并查集（Union-Find）详解：附代码

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

什么是并查集？

并查集，也称不相交集合并（DSU），是一种数据结构，用来跟踪被划分为互不重叠分组的一批元素。每个元素恰好属于一个组，每个组由唯一的代表元（它的根）来标识。

诀窍在于分组的存储方式：作为一片树的森林。每个元素持有一个指向父节点的指针，沿着父节点一路向上总会到达该组的根。两个元素在同一组当且仅当它们共享同一个根。这就是全部思想，其余一切都是为了让它变快。

两个操作

并查集恰好支持两个操作，它的全部名声都系于把这两件事几乎瞬间完成。

• find(x) 沿父指针向上，返回包含 x 的组的根。当 find(a) == find(b) 时，两个元素连通。
• union(a, b) 通过让一个根成为另一个根的父节点，合并两个组。

由于分组只会合并、从不拆分，并查集非常适合那些连接随时间加入、却从不移除的问题。

朴素版本及其问题

第一次尝试只是存储父指针，通过让一个根指向另一个根来合并。它能用，但有一个糟糕的失效模式：没有什么能阻止树长成长链。如果每次 union 都把一个节点摞在上一个之上，find 就得走一条长度为 n 的链，每次操作退化到 O(n)。

那并不比一个普通列表更好。解决办法是两处小改动，它们合在一起是数据结构中最著名的成果之一。

改变一切的两个优化

按秩合并让树保持浅。合并两个组时，总是把较矮的树挂到较高那棵树的根下。矮树挂在高树上不会增加高度，所以树保持扁平。

路径压缩边走边压平。每次 find 向上走到根时，它把途经的每个节点都直接指向那个根。之后对其中任意一个再做 find 就只是一跳。下图展示了一次 find 把一条链坍缩。

按秩合并与路径压缩一起使用，能让每棵树几乎完全扁平，因此两个操作都以近乎常数的时间运行。单用其一有帮助；两者合用才是并查集出名的原因。

Python 实现

整个结构装进一个小类。两个数组完成全部工作：parent 和 rank。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # 每个元素起初都是自己的根
        self.rank = [0] * n            # 每棵树高度的一个上界

    def find(self, x):
        # 路径压缩：把 x 直接指向根。
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # 已经在同一组

        # 按秩合并：把较矮的树挂到较高的树下。
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

注意，当两个元素本已连通时，union 返回 False。正是这一个布尔值让环检测和 Kruskal 算法如此干净：如果一次 union 失败，你正要加入的那条边就会闭合一个环。

复杂度：几乎常数

同时使用两个优化时，对 n 个元素做 m 次操作的总时间为 O(m · α(n))，其中 α 是反阿克曼函数。

反阿克曼函数增长得如此之慢，以至于对任何塞得进可观测宇宙的 n，α(n) 至多为 4。实践中，把每次操作当作常数时间即可。要看它在所有图算法中的位置，见复杂度指南和速查表。

它用在哪里

凡是需要在连通性不断增长时对其进行跟踪的地方，都会出现并查集。

• Kruskal 最小生成树：先对边排序，然后仅当一条边的两端在不同组时才加入它。并查集就是那个环检查。见最小生成树。
• 无向图中的环检测：对每条边，若两端已共享同一个根，这条边就闭合一个环。
• 连通分量：对每条边做 union，然后数不同的根的个数。
• 动态连通性与面试：诸如 Number of Provinces、Redundant Connection 和 Accounts Merge 之类的题，本质上都是并查集。见编程面试图算法。

它还位于图论学习路线图的第 3 阶段，正是你学习生成树的地方。