并查集深度实战：从等价划分、路径压缩到按秩合并与可撤销/持久化的工程全解
并查集（Disjoint Set Union，DSU / Union-Find）是计算机科学里最被低估的基础数据结构之一。它解决的问题极其朴素：维护一个不断合并的等价类划分，并在近乎常数时间内回答"这两个元素是否属于同一集合"。Kruskal 最小生成树、连通分量、图像分割、离线动态连通性、等式/不等式约束满足、类型合一、垃圾回收的可达性分析——背后都是它。
有趣的是，一个看似 O(n) 的朴素结构，只要加上两个各写一行的小优化（路径压缩 + 按秩/大小合并），其摊还复杂度就被压到反阿克曼函数 α(n)，这个值在物理可观测的宇宙尺度内不超过 5。本文从第一性原理出发，推导它的正确性边界，给出可插拔的工业级 Python 实现，并系统梳理加权并查集、可撤销并查集、持久化并查集、DSU on tree、动态连通性等变体的工程取舍与 12 项生产陷阱。
一、第一性原理：等价关系与森林表示
并查集维护的是集合上的一个划分（partition）。划分的数学本质是等价关系（自反、对称、传递）：一旦 a~b 且 b~c，就必须有 a~c。朴素做法用哈希表记录每个元素的类标签，合并时把一整类的标签改写——最坏 O(n) 每步。
并查集的巧妙之处在于用有根森林表示划分：每个集合是一棵树，树根即"代表元（representative）"。两个操作由此定义：
find(x)：沿父指针爬到根，返回根作为集合代表元。union(x, y)：找到各自的根，若不同则将一棵树的根挂到另一棵树的根下，完成合并。
初始时每个元素自成一树（parent[x] = x）。connected(x, y) 等价于 find(x) == find(y)。
判断"两个元素是否连通"被转化为"它们的根是否相同"，而"合并两棵树"只是改一个指针。复杂度完全取决于树的高度——这正是后面两个优化要解决的。
二、朴素实现的退化陷阱
最直观的实现完全正确，却藏着 O(n) 的地雷：
class NaiveDSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
x = self.parent[x] # 一路向上爬
return x
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx != ry:
self.parent[rx] = ry # 随便挂，不管高度
如果每次都 parent[rx] = ry（不比较大小），连续合并会把树退化成一条链（典型构造：依次 union(0,1), union(1,2), union(2,3)...）。此时 find 退化为 O(n)，n 次操作总复杂度 O(n²)。在 n=10⁶ 时这完全不可接受。
三、核心优化一：按秩合并 / 按大小合并
思路：合并时总是把较矮（或较小）的树挂到较高（或较大）的树下，避免人为拔高树高。
- 按秩（rank）合并：维护"近似高度" rank，挂树时 rank 小的挂到大的下面；仅当两 rank 相等时挂上去后根 rank+1。rank 是高度的严格上界。
- 按大小（size）合并：维护子树元素个数 size，小的挂到大的下面。实现更简单，且对路径压缩同样友好。
两者理论等价（都保证树高 O(log n)），工程上 size 更直观。仅此一项，不加路径压缩，单次 find 已被压到 O(log n)。
四、核心优化二：路径压缩
find 时把所有被访问的非根节点直接重连到根，扁平化路径：
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root]
# 路径压缩（迭代，避免递归爆栈）
while self.parent[x] != root:
self.parent[x], x = root, self.parent[x]
return root
路径压缩把"爬过的路径"压平，下次查询这些节点就是 O(1)。单独使用路径压缩（不按秩合并）仍可能被聪明构造的合并序列退化成 O(log n) 级别；但与按秩合并同时使用时，二者相互校验，把摊还复杂度钉死在 α(n)。
递归写法
return x if parent[x]==x else parent[x]=find(parent[x])在 Python 里是雷区：路径压缩最坏会沿一条链递归，深度超过默认 1000 就会RecursionError。生产环境一律用迭代版。
五、复杂度证明：为什么是 α(n)
Tarjan 在 1975 年证明：使用路径压缩 + 按秩合并的并查集，m 次操作（含 n 次 make-set）的摊还时间复杂度为 O(m · α(n))，其中 α 是阿克曼函数 A 的反函数：α(n) = min{k | A(k, k) ≥ n}。
直觉：按秩合并保证树高受控，路径压缩又把"曾经被查过"的路径压平。二者叠加后，一个节点的父指针被改变的次数（即它被压缩的次数）被其到根的距离上界严格限制，经过精细的势能分析可得每次操作摊还 O(α(n))。
α 的增长慢到荒谬：A(1,1)=3, A(2,2)=7, A(3,3)=61, A(4,4) 已是 2^2^65536 量级的巨数。因此对于任意物理可实现的 n（远小于 2^65536），α(n) ≤ 4。也就是说，在工程实践中并查集的 find 近似常数时间。这不是"平均"，是严格摊还上界。
六、可插拔工业级实现
下面给出一个支持路径压缩 + 按大小合并、可返回"是否真的合并了"语义、并预留回滚钩子的实现：
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self._ops = [] # 仅在需要可撤销时启用
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root: # 迭代路径压缩
self.parent[x], x = root, self.parent[x]
return root
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # 已在同集合
# 按大小合并：小树挂大树
if self.size[rx] < self.size[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
self.size[rx] += self.size[ry]
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
要点：
union返回布尔值，统一"是否发生真实合并"的语义，方便 Kruskal 之类的计数。- 用 list 预分配 parent/size，避免 dict 的哈希开销；n 很大时这能带来数倍提速。
- 节点下标统一从 0 开始；若业务是 1-based，调用前
-1，或在构造时n+1。
七、变体谱系：从加权到持久化
7.1 加权并查集（扩展域 / 带权）
普通并查集只表达"是否同类"。当约束是带权关系或多类互斥（如"敌人、朋友、自己"三态）时，使用扩展域：把每个元素 x 拆成 k 个逻辑节点（x_0, x_1, ... x_{k-1}）映射到同一森林，原问题转化为普通连通性。经典应用是"种类并查集"（食物链题：同类 / 吃 / 被吃三种关系）。另一种带权形式是维护 diff[x] = value(x) - value(parent[x])，合并时按方程更新差值，用于区间等式、模运算同余类。
7.2 可撤销并查集（Rollback DSU）
某些离线算法需要"撤销最近的若干次合并"（如按时间分治的动态连通性、带撤销的强连通分量）。关键约束：可撤销时不能做路径压缩——压缩会改写历史父指针，无法干净回滚。正确做法是只做按大小合并，并把每次合并的 (小根, 大根, 旧 size) 压入栈；撤销时 parent[小根]=小根; size[大根]-=旧size 即可，单步 O(1)。
7.3 持久化并查集（Persistent DSU）
需要"回到历史某一版本的连通状态"时，用可持久化数组（基于可持久化线段树或分块）存储每一版本的 parent/size。合并产生新版本（路径上节点复制，O(log n) 额外空间）。注意持久化版本通常也放弃路径压缩以保证版本间独立性，复杂度 O(log n) 每操作。
7.4 DSU on Tree（树上启发式合并）
对静态树上"每个子树内出现次数最多的颜色"这类问题，把子树信息用并查集/桶维护，每次只保留重儿子（heavy child）的状态、轻儿子重新插入，将复杂度从 O(n²) 降到 O(n log n)。本质是把并查集当作"集合合并 + 查询"的工具嵌入树形 DP。
7.5 动态连通性（离线）
在线支持加边 / 删边的连通性查询是难题；经典离线解是 Euler tour tree / link-cut tree + 并查集分治：把时间轴按"边是否存活"分治，用普通并查集在分治区间内回答"该边全程存活则连通"。这是并查集从静态走向动态的桥梁。
7.6 网格并查集
二维网格（如 percolation、岛屿数量、图像连通域）把 (r,c) 映射到 r*W+c 一维下标，即可复用一维并查集。注意网格坐标到下标的映射要一致，否则会出现"跨行误连"。
八、关键应用速查
| 应用 | 用法 | 备注 |
|---|---|---|
| Kruskal MST | 边按权排序，union 成功才计入 | O(E log E) 主导在排序 |
| 连通分量 / 孤岛 | 逐边 union，最后按根分组 | 比 BFS 省内存 |
| 图像分割 | Felzenszwalb 基于区域相似度贪心合并 | 实时分割经典算法 |
| 离线动态连通 | 分治 + 回滚并查集 | 在线版本需 LCT |
| 等式约束满足 | 相等变量 union，冲突检测 | 与 2-SAT 区分 |
| 类型合一 / GC | 变量等价类合并 | 编译器与运行时基础设施 |
| 带权同余 | 扩展域 + 差值维护 | 模方程、差分约束 |
九、12 项生产陷阱清单
- 递归路径压缩爆栈：Python 默认递归深度 1000，链状压缩直接
RecursionError。一律用迭代压缩。 - 忘记按秩/大小合并：只做路径压缩仍可被构造退化；二者必须同时启用才能锁死 α(n)。
- 0/1 索引混淆：业务 1-based 而实现 0-based，导致下标错位或越界。统一在入口转换。
- find 未压缩：写成
while parent[x]!=x: x=parent[x]; return x忘了回写，等于没优化。 - union 语义不统一：有的返回是否合并、有的不返回，调用方计数错误。固定返回 True/False。
- 扩展域偏移算错：种类并查集把 x 拆成 k 份，索引
x*k + t若越界或重复会静默错误。 - rank 与 size 混用：按秩合并维护 rank，按大小合并维护 size，混用会让"高度上界"失效。
- 可撤销时误用路径压缩：压缩改写历史父指针，撤销不干净。回滚场景只用按大小合并 + 栈记录。
- 持久化版本数失控：每次合并复制路径 O(log n) 节点，版本过多内存爆炸；评估保留窗口。
- 多测试用例未重置：全局 parent/size 残留上一组结果，表现为"莫名其妙连通"。每组重初始化。
- 并发非安全：并查集不是并发安全的，多线程同时 union 会出现竞态丢合并。加锁或按分片隔离。
- 用 dict 代替数组：n 已知且稠密时 list 远快于 dict；稀疏超大 id 才考虑 dict 或坐标压缩。
十、与本站其他结构的职责对照
| 结构 | 核心能力 | 与并查集的关系 |
|---|---|---|
| 并查集 | 动态合并等价类、连通性 | 本文主角 |
| BFS/DFS 连通 | 一次性遍历 | 静态图更省，动态合并无能 |
| 线段树 | 区间查询/修改 | 职责正交，可配合 DSU on tree |
| 树状数组 | 前缀和/单点更新 | 不参与集合合并 |
| 跳表 / 平衡树 | 有序动态集合 | 不表达等价类 |
| 布隆/CMS/HLL/布谷鸟 | 概率/近似集合成员 | 见本站"概率与高性能数据结构工程"系列，与并查集互补：后者是确定性、精确的集合划分 |
十一、生产可复现工具箱
下面把"路径压缩 + 按大小合并 + 可撤销钩子"打包成一个可直接落地的工具类，覆盖 90% 生产场景：
class ProductionDSU:
def __init__(self, n, reversible=False):
self.parent = list(range(n))
self.size = [1] * n
self.reversible = reversible
self._stack = [] # 仅 reversible 时使用
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root:
self.parent[x], x = root, self.parent[x]
return root
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
if self.reversible:
self._stack.append(None) # 标记"无操作"
return False
if self.size[rx] < self.size[ry]:
rx, ry = ry, rx
if self.reversible:
self._stack.append((ry, rx, self.size[rx]))
self.parent[ry] = rx
self.size[rx] += self.size[ry]
return True
def undo(self):
if not self.reversible or not self._stack:
return
op = self._stack.pop()
if op is None:
return
ry, rx, old_sz = op
self.parent[ry] = ry
self.size[rx] = old_sz
构造时传 reversible=True 即获得 O(1) 回滚能力（注意此时自动放弃路径压缩以保证可撤销性）。配合本文第九节清单逐项排查，即可把并查集稳定地落到生产系统。
十二、结语
并查集是"小结构、大思想"的典范：两行优化（路径压缩 + 按秩合并）把朴素 O(n²) 压到 α(n) 的近常数；而一旦理解其变体谱系——加权扩展域、可撤销、持久化、DSU on tree、动态连通性——它就从"算法竞赛 trick"蜕变为编译器、运行时、图像系统与分布式一致性的底层基础设施。它与本站已发布的布隆过滤器、Count-Min Sketch、HyperLogLog、布谷鸟哈希共同构成"概率与高性能数据结构工程"系列，前者提供确定性、精确的等价类划分，后者提供概率、近似的集合成员/频率/基数估计，二者在工程栈中互补共存。下一步可继续补全线段树、树状数组等经典确定结构，完成"数据结构工程"全谱系。
发表评论 取消回复