c++ - 根据公共(public)元素组合成对的整数

Question

假设我有一对整数，例如 (1,3)、(5,6)、(7,8)、(3,9)，然后我想根据它们之间的共同元素将这些对组合成独特的集合即我可以组合 (1,3) 和 (3,9) 因为 3 在它们之间是通用的，所以上面输入的最终输出应该是这样的 (1,3,9), (5,6), (7,8 )一种方法可能是遍历此数组并基于公共(public)元素将其组合并从数组中删除第二对，我认为这很耗时。在 C/C++ 中执行此操作的有效方法是什么？

Answer 1

执行此操作的一种有效方法是将其视为图形连接问题。创建一个图，其中节点是整数对，如果它们对应的对具有公共(public)元素，则在两个节点之间添加一条无向边。现在，找到这个图中的连通分量，并构造由分量中的节点对应的对的并集形成的集合。

寻找连通分量需要 O(E) 时间，如果有 n 对，则可能是 O(n^2)。可以使用类似于 heap 的结构将它们全部合并，每次插入需要 O(log n)。因此，运行时间是 O(E + n log n)，最多是 O(n^2)。根据有多少对具有共同元素，复杂度可能会低得多。