给定一个集合列表：
合并所有共享至少 2 个元素的集合的最有效方法是什么？我想这类似于连接组件问题。所以结果是：
朴素的实现是 O(N^2)，其中 N 是集合的数量，这对我们来说是行不通的。这需要对数百万组有效。
Let there be a list of many Sets named (S)
Perform a pass through all elements of S, to determine the range (LOW .. HIGH).
Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).
do
Init all elements of M to NULL.
Iterate though S, processing them one Set at a time, named (Si).
Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
For each pair examine M(P1, P2)
if M(P1, P2) is NULL
Continue with the next pair.
otherwise
Merge Si, into the Set pointed to by, M(P1, P2).
Remove Si from S, as it has been merged.
Move on to processing Set S(i + 1)
If Si was not merged,
Permutate again through Si
For each pair, make M(P1, P2) point to Si.
while At least one set was merged during the pass.
我的头是说这是关于订单（2N ln N）。带着一粒盐。
如果您可以对集合中的元素进行排序，则可以考虑在集合上使用Mergesort。唯一需要的修改是在合并阶段检查重复项。如果找到，只需丢弃重复项。由于归并排序是 O(n*log(n))，与朴素的 O(n^2) 算法相比，这将提供改进的速度。
但是，要真正有效，您应该维护一个排序集并使其保持排序，这样您就可以跳过排序阶段并直接进入合并阶段。
我看不出这如何在少于 O(n^2) 的时间内完成。
每个集合都需要与其他集合进行比较，以查看它们是否包含 2 个或更多共享元素。这是 n*(n-1)/2 比较，因此 O(n^2)，即使检查共享元素需要恒定时间。
在排序中，简单的实现是 O(n^2) 但您可以利用有序比较的传递性（例如，您知道快速排序的下分区中的任何内容都不需要与上分区中的任何内容进行比较，因为它已经与枢轴进行了比较）。这就是排序为 O(n * log n) 的原因。
这不适用于这里。因此，除非集合有什么特别之处，可以让我们跳过基于先前比较结果的比较，否则它通常会是 O(n^2)。
保罗。
附注：这取决于这种情况发生的频率。如果大多数集合对确实共享至少两个元素，那么在您逐步进行比较的同时构建新集合可能是最有效的，如果它们不符合条件则将其丢弃。如果大多数对不共享至少两个元素，那么将新集合的构建推迟到条件确认后可能会更有效。
如果您的元素本质上是数字的，或者可以自然排序（即，您可以分配一个值，例如 1、2、42 等...），我建议对合并集使用基数排序，然后再做一个传球以了解独特的元素。
该算法应该是 O(n)，并且您可以使用按位移位运算符和位掩码对基数排序进行相当多的优化。我为我正在做的一个项目做了类似的事情，它就像一个魅力。