Как эффективно объединить все пересекающиеся векторы?

Допустим, у меня есть вектор векторов:

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) без эвристики).

Мне нужно сделать это эффективно, поэтому я имею в виду, что нужно перебрать все узлы и записать, где я нашел исходный узел, а затем сгруппировать их вместе в одном поиске, если это возможно.
Однако я не могу найти и разработать такой алгоритм, чтобы он был достаточно эффективным, поэтому я был бы признателен за некоторую помощь или идеи о том, как подойти к этому.

Спасибо.

2

Решение

Задача ещё не решена.

Другие решения


По вопросам рекламы [email protected]