2

假设我有一个向量向量:

std::vector<std::vector<int> > vec;

现在,在我的程序中,该向量包含在图中创建循环的节点组。如果它们相交,它们将创建强连通分量。

我需要遍历这个向量并有效地找到那些相交的向量,然后加入这些向量。可以通过蛮力 set_intersection 和 set_union 使用集合来完成,但它会很慢。

例如,如果我有简单 int 元素的向量 AD,其中 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(N 2 ) 没有启发式)。

我需要有效地做到这一点,所以我想到的是遍历所有节点并记下我找到原始节点的位置,然后在一次搜索中将它们组合在一起,如果可能的话。但是,我无法找到也无法设计出足够有效的算法,因此我将不胜感激有关如何解决此问题的一些帮助或想法。

谢谢你。

4

0 回答 0