并查集（Union-Find）详解：原理、代码与时间复杂度

并查集解决什么问题

设想一个计算机网络，网线一根一根地接上去，每接一根之后，你都要回答“计算机 A 和计算机 B 连通吗？”。每个问题都做一次图搜索，每次要花 O(n + m)。并查集在加线的同时维护连通的分组，几乎能在 O(1) 内回答每个问题。

同样的需求还出现在 Kruskal 最小生成树算法中（这两个端点是否已经属于同一棵树？）、检测无向图中的环、合并共用同一个邮箱的账号、渗流模拟，以及图像处理中标记连通区域。

用大白话理解并查集

每个元素都指向一个父节点。指向自己的元素是根，根就是整个分组的代表。要找到 x 所在的分组，就沿着父指针一路走到根。要合并两个分组，就找到两个根，让其中一个根指向另一个。

两个优化让树保持扁平：

• 按秩（或按大小）合并：把较矮（或较小）的树挂到较高（或较大）的树下面，这样只有当两棵相同的树合并时，树的高度才会增长。
• 路径压缩：在 find 过程中，让路径上的每个节点都直接指向根，这样下一次查找只需一步。

示例演练：五个元素

从元素 0 到 4 开始，每个元素各在自己的分组里。父数组是 [0, 1, 2, 3, 4]。我们使用按大小合并，大小相等时让第二个根成为孩子。

Python 实现

这个版本使用按大小合并，以及带路径压缩的迭代式 find，所以不存在递归深度问题。当两个元素本来就在同一分组时，union 返回 False，这对检测环很有用。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.groups = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:       # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                    # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                 # ra is the larger root
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.find(3), uf.parent)       # 0 [0, 0, 0, 0, 4]
print(uf.connected(1, 4), uf.groups)  # False 2

示例：检测无向图中的环

逐条处理边。如果一条边的两个端点已经有相同的根，这条边就闭合了一个环。Kruskal 算法在按权重对边排序之后，用的正是这个检查。

def has_cycle(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return True
    return False

print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))  # False
print(has_cycle(4, [(0, 1), (1, 2), (2, 0)]))  # True

时间与空间复杂度

α(n) 是反阿克曼函数，它增长得极其缓慢，对于真实计算机能容纳的任何 n，它最大也不超过 4。实际上这意味着每次操作都是常数时间。Robert Tarjan 在 1975 年证明了这个上界。空间是 O(n)，用于父数组和大小数组。

变体与常见错误

• 比较元素而不是比较根：union 必须连接 find(a) 和 find(b)，而不是 a 和 b 本身。
• 以为 parent[x] 就是代表元素。合并之后，只有 find(x) 才是正确的；按父节点分组之前，要对每个元素调用 find。
• 在大输入上使用递归的 find 又不做按秩合并，可能触及 Python 的递归限制；上面的迭代版本可以避免这一点。
• 元素不是 0 到 n-1 的整数：先用 dict 把它们映射为下标，或者把父节点存在 dict 中并惰性地添加元素。
• 并查集无法拆分分组。如果要删除边，就需要不同的数据结构，或者采用按相反顺序处理删除的离线方法。
• 带权并查集在每个节点上保存到父节点的偏移量，可以回答“a 比 b 重多少？”这类问题。

何时使用，以及典型问题

当分组只会合并，并且你需要询问两个元素是否在同一分组，或者一共有多少个分组时，请使用并查集。对于静态图上的一次连通性问题，普通的 BFS 或 DFS 更简单。需要真正的路径时，请使用图搜索，因为并查集只知道成员归属。

典型问题：连通分量的数量、岛屿数量（把网格单元当作元素）、冗余连接（造成环的那条边）、账户合并、a == b, b != c 这类等式方程的可满足性，以及 Kruskal 最小生成树。