并查集：把等价关系收进森林

1. 问题描述

维护一组元素的动态等价关系，支持两种操作：

• union(a, b)：把 a、b 所在的集合合并；
• find(a)：返回 a 所在集合的代表元（根）。

判等价 = find(a) == find(b)。连通性、分组、环检测（逐条加边，两端已同集即成环）都能归到这个模型。

2. 直觉：一棵随时可以变形的树

用「指向父亲」的数组 parent 表示森林：每个集合是一棵树，树根充当代表元。find 沿父指针爬到根；union 把一棵树的根挂到另一棵树的根下。

变形是允许的——树长什么样不重要，重要的是：

这个不变量只关心「同根」，不关心路径长短。于是我们可以理直气壮地压扁路径：find 的路上顺手把每个结点直接挂到根上（路径压缩），树变浅，不变量毫发无损。

3. 两个优化与 α(n)

1. 路径压缩：find 时把沿途结点的父指针全部改为根；
2. 按大小合并（或按秩）：永远把小树挂到大树底下，避免森林退化成链。

两个优化叠加后，单次操作的均摊复杂度是 $O(\alpha(n))$——阿克曼函数的反函数，对一切现实规模的 $n$ 都 $\le 4$，工程上视作常数。

注意一个细节：用了路径压缩后，「按秩」里的 rank 就不再是准确的高度，只是一个足够好用的估计——它只用于合并时的比较，不影响正确性（正确性只靠 §2 的不变量）。

4. 代码实现

1class UnionFind:2  def __init__(self, n: int):3      self.parent = list(range(n))   # 初始每个元素自成一棵树4      self.size = [1] * n            # 按大小合并用的估计值5 6  def find(self, x: int) -> int:7      root = x8      while self.parent[root] != root:9          root = self.parent[root]10      while self.parent[x] != root:  # 路径压缩:第二次爬,逐个挂到根11          self.parent[x], x = root, self.parent[x]12      return root13 14  def union(self, a: int, b: int) -> bool:15      ra, rb = self.find(a), self.find(b)16      if ra == rb:17          return False               # 已同集,合并无效果18      if self.size[ra] < self.size[rb]:19          ra, rb = rb, ra            # 保证 ra 是大树,把小树 rb 挂上去20      self.parent[rb] = ra21      self.size[ra] += self.size[rb]22      return True

5. 边界与常见错误

• 自环 / 重复边：union(a, a) 直接无害返回 False，无需特判；
• 合并方向写反：parent[ra] = rb 与大小判断不一致时，优化失效（复杂度退化，但不影响正确性——不变量仍在）；
• 把结点挂到非根上：parent[a] = rb（挂到了 b 而不是 b 的根），这会破坏不变量，是最危险的笔误；
• 忘记初始化 size：按大小合并退化成随机方向。

6. 相关练习

• LeetCode 547 · 省份数量——union + 数根的个数；
• LeetCode 684 · 冗余连接——第一条使两端已连通的边；
• LeetCode 128 · 最长连续序列——哈希 + 并查集两种视角的对照。

下一篇建议读 043《单调栈：下一个更大元素》。