从 C++ 中的对向量生成组向量

Question

我有一个整数对向量，看起来像这样：

pair[0] = {1, 2}
pair[1] = {5, 7}
pair[2] = {9, 3}
pair[3] = {4, 6}
pair[4] = {8, 6}
pair[5] = {1, 3}
pair[6] = {9, 6}

我需要将任意对中的数字组合在一起。

例如，数字 1 与 2 和 3 配对，因此它们属于一个组。 3也和9配对，9和6配对，6和4配对，所以他们也需要是第一组的一部分。

数字 5 和 7 与第一组中的任何其他数字都不重叠，因此需要将它们放在自己的组中。

生成的向量需要类似于：

group[0] = {1, 2, 3, 4, 6, 8, 9}
group[1] = {5, 7}

我想要这个，我想要一个有效的方式。谢谢。

Answer 1

直接应用Disjoint-set Data Structure即可解决此问题。

遍历对列表，并为找到的每个数值创建一个单例集。然后再遍历一次对，对由每对的两个元素表示的集合执行 union 操作。

鉴于文章中描述的正确表示，这可以在线性时间和 space 中非常有效地完成。