Допустим, у меня есть вектор векторов:
std::vector<std::vector<int> > vec;
Теперь в моей программе этот вектор содержит группы узлов, которые создают цикл в графе. Они создают сильно связанный компонент, если они пересекаются.
Мне нужно перебрать этот вектор и эффективно найти те векторы, которые пересекаются, а затем присоединяются к ним. Это можно сделать с помощью наборов с помощью грубой силы set_intersection и set_union, но это будет очень медленно.
Например, если у меня есть векторы A-D простых элементов int, где A, B, D пересекаются.
A = [1,2,3,4]
B = [5,6,7]
C = [8,9]
D = [3,4,6,10]
и я хочу этот результат:
s1 = [1,2,3,4,5,6,7,10]
s2 = [8,9]
Теперь, я пробовал несколько вещей за последние несколько часов, но простое прибегание к поиску показывает, что set_intersection будет довольно медленным подходом, и мне придется обходить все наборы узлов несколько раз (я думаю, что это будет N * (N + 1) / 2, поэтому O (N2) без эвристики).
Мне нужно сделать это эффективно, поэтому я имею в виду, что нужно перебрать все узлы и записать, где я нашел исходный узел, а затем сгруппировать их вместе в одном поиске, если это возможно.
Однако я не могу найти и разработать такой алгоритм, чтобы он был достаточно эффективным, поэтому я был бы признателен за некоторую помощь или идеи о том, как подойти к этому.
Спасибо.
Задача ещё не решена.