C++ Найти транзитивные элементы

Вообще, вашу задачу намного удобнее рассматривать в графовом виде. У вас есть список ребер, необходимо найти цикл длины три (ну или полный подграф из трех вершин, все равно треугольник - он и есть треугольник). Ю

Тогда могу предложить два варианта: O(E^2logE) и O(V^3logE), где E - количество ребер, V - количество вершин. На плотных графах быстрее будет второй, а на разреженных - первый.

Upd: Глянув ссылку MBo я понял, что мой первый имеет сложность O(VElog(E)), но с большей константой.

Первый грубо выглядит так:

1. Создать список инцидентности или как он там называется, 
то есть `vector<vector<int>> g`, в котором `g[v]` обозначает список смежных с `v` вершин. 
2. Отсортировать все g[i].
3. Для каждого ребра {v, u} попытаемся найти вершину x такую, что x in g[v] и x in g[u]:
3.1. Пройдем двумя указателями по отсортированным массивам g[v] и g[u]. 
Если в какой-то момент окажется, что оба указателя показывают на одно и то же число, оно и будет искомой вершиной x. 
Если же такого не произойдет, то не существует треугольника, содержащего ребро {v, u}.
4. Ну мы нашли треугольник из вершин v, u, x. 
Теперь можно просто полным проходом по списку edges найти индексы пар {v, u}, {u, x}, {v, x}. 
Кстати, для удобства этого этапа можно отсортировать числа в каждой паре из edges.

Второй так:

1. Сжимаем вершины для удобства их перебора.
2. Снова создаем список инцидентности, но теперь с использованием set, то есть vector<set<int>> g.
3. Перебираем все тройки вершин i, j, k. Проверяем `j in g[i] & k in g[i] & k in g[j]`. 
4. Найдя нужные вершины i, j, k, можем снова проходом по edges найти индексы соответствующих ребер.

Если будет что-то непонятно, могу объяснить или дополнить кодом, но позже.

Эта задача связана с Triangle-free graph. В статье можно найти упоминание алгоритма для поиска треугольника в графе за время O(M^1.41), M - число ребер. В нашем случае число ребер мало, можно построить алгоритм который работает за O(M).

Алгоритм ожидает что вершины графа - целые в диапазоне [0, 15]. Поиск треугольника делается битовыми операциями.

Наличие треугольника проверяется после добавления следующего ребра. Этого достаточно, треугольник будет найден как только будет обработано его третье ребро.

Граф строится и хранится в битовой матрице смежности bits. Вторая матрица edges хранит номера ребер. Для обнаружения треугольника она не нужна, ипользуется только для печати ответа - в ответе номера ребер.

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror example.cpp

#include <cassert>
#include <iostream>

const unsigned N_VERTICES = 16;
typedef uint16_t bitset_t;
typedef uint8_t vertex_t;
typedef uint8_t edge_t;
struct pair_t {
    vertex_t a;
    vertex_t b;
};

vertex_t some_bit_index(bitset_t n) {
    vertex_t c = 0;
    for (; (n & 1) == 0; n >>= 1) {
        ++c;
    }
    return c;
}

bool triangle(edge_t m, const pair_t pairs[/* m */], edge_t answer[3]) {
    edge_t edges[N_VERTICES][N_VERTICES]; // intentionally uninitialized
    bitset_t bits[N_VERTICES] = {0};
    for (edge_t i = 0; i < m; ++i) {
        const vertex_t j1 = pairs[i].a;
        assert(j1 < N_VERTICES);
        const vertex_t j2 = pairs[i].b;
        assert(j2 < N_VERTICES);
        bits[j1] |= 1 << j2;
        bits[j2] |= 1 << j1;
        edges[j1][j2] = edges[j2][j1] = i;
        const bitset_t intersection = bits[j1] & bits[j2];
        if (intersection != 0) {
            const vertex_t j3 = some_bit_index(intersection);
            answer[0] = edges[j1][j3];
            answer[1] = edges[j3][j2];
            answer[2] = edges[j2][j1];
            return true;
        }
    }
    return false;
}

int main() {
    const pair_t pairs[] = {
        { 0,  2},
        {12,  2},
        { 4,  3},
        {12,  0},
        { 5, 11},
        { 6,  2}
    };
    const edge_t m = sizeof pairs / sizeof(pairs[0]);
    edge_t answer[3];
    const bool found = triangle(m, pairs, answer);
    std::cout
        << (found ? "yes" : "no") << ' '
        << static_cast<int>(answer[0]) << ' '
        << static_cast<int>(answer[1]) << ' '
        << static_cast<int>(answer[2]) << '\n'
    ;
}

Производительность проверялась на двух типах случайных графов. Первый тип - треугольник из трёх ребер. Второй - двудольный граф. Обе доли по восемь вершин - 64 ребра. Ещё одно ребро добавлялось внутри одной доли чтобы появился один треугольник. Результаты:

random min graph (3 edges) 29.1ns, 34395659.3 graphs/s
random max graph (65 edges) 232.7ns, 4296952.3 graphs/s

Производительность в диапазоне 4-34 миллиона графов в секунду.

Есть возможности для улучшения. Функция some_bit_index может быть аппаратно ускорена c помощью __builtin_clz или чего-то подобного.

bitset_t bits[N_VERTICES] = {0}; - очищает целиком весь граф. Если в графе мало вершин, это может быть слишком накладно.

Технология масштабируется до графов с 64-мя вершинами.