一文搞懂并查集进阶：路径压缩与按秩合并如何把连通判定优化到近 O(1)

判断「两个元素是否属于同一个集合」，听起来是个再朴素不过的需求，但它几乎藏在所有系统的角落里：社交网络要判定两个用户是否在同一个好友圈，编译系统要检测依赖图有没有成环，网络运维要确认两台机器是否可达，风控系统要把同一设备登录过的一串账号合并成一个团伙。这些问题的共同形态是：元素之间不断发生「合并」，又要随时回答「谁和谁连通」。

并查集（Union-Find）就是为这种动态连通性量身定做的结构：两个操作、几行代码，就能在近乎常数的时间内完成合并与查询。但很多人对它的理解停留在「背模板」层面——知道要写 find 和 union，却不清楚路径压缩与按秩合并为什么能让单次操作均摊复杂度降到近乎常数，于是换一道变形题（比如带权并查集、种类并查集）就无从下手。这篇文章从朴素实现的缺陷讲起，把两大优化的推导、完整实现与应用一次讲透。

问题背景：朴素并查集为什么会退化成一条链

并查集用一片森林表示所有集合：每个元素记录自己的父节点，根节点的父节点指向自己，两个元素在同一棵树上等价于属于同一个集合。判断连通只需要各自向上找到根再比较；合并则是把一棵树的根挂到另一棵树的根下面。

问题出在「挂」的方向上。朴素的合并如果不加约束，最坏情况会让树退化成一条链：依次执行 union(0,1)、union(1,2)、union(2,3)……如果每次都让「新集合的根」指向「旧集合里编号更小的节点」，恰好就会得到 0←1←2←3 这样一条链。此时对链条最底端的元素做一次 find，要走完整条链，代价 O(n)；n 次这样的查询叠加起来，总代价直接到 O(n²)。

在 n 是几十万的真实场景里，这种退化是致命的。比如对十万条账号关联记录做团伙分析，朴素并查集可能比带优化的版本慢上百倍。更麻烦的是退化是「悄悄发生」的：小数据测试一切正常，数据量一大性能就断崖式下跌。所以两大优化不是锦上添花，而是并查集能上生产的前提。

思路推导：两大优化如何把树压到几乎两层

优化一：路径压缩。 思路是在 find 的过程中顺手「修理」这棵树——找到根之后，把沿途经过的所有节点全部改为直接指向根。这样一来，第一次 find 某条长链虽然要付出 O(链长) 的代价，但走完之后整条链上的节点都变成了根的直接子节点，树高从 n 陡降到 2。下一次再查这些节点，就是一步到位。也就是说，一次 find 的代价不会白花，它让整棵树「越用越扁」，把成本摊销到了后续无数次查询上。

优化二：按秩合并（或按大小合并）。 路径压缩解决的是「查询侧」的树高问题，但两棵树合并时如果总让大树挂到小树下，树高同样会失控。按秩合并的规则很简单：合并时把「矮」的树挂到「高」的树下面（按大小合并则是把元素少的挂到元素多的下面）。可以证明这样维护出来的树高始终是 O(log n) 级别——每让一个节点的「深度」增加一层，它所在树的规模至少翻一倍，而规模最多翻 log n 次。

两者叠加的效果。 单独用按秩合并，树高 O(log n)；单独用路径压缩，均摊性能已经很好；两个一起用，单次 find/union 的均摊复杂度是 O(α(n))——α 是反阿克曼函数，增长慢到对宇宙内任何实际数据规模（n ≤ 10^80）它的取值都不超过 4。工程上完全可以把它当常数看待，这就是「近 O(1)」的含义。

这里有一个大多数文章没讲清的细节：路径压缩会改变树的形状，但不会同步更新「秩」的数值，所以严格实现里按秩合并的「秩」其实只是树高的一个上界估计，而不是精确高度。这完全不影响正确性——秩的作用只是引导合并方向，估计得保守一点，合并出来的树照样够矮。理解了这一点，再看不同教材里「rank 有时对不上真实树高」的现象就不会困惑了。

实操代码：完整实现与三类连通性应用

下面是带路径压缩 + 按大小合并的完整 Python 实现，find 用迭代而非递归，避免长链下的递归栈溢出：

class UnionFind:
    """带路径压缩 + 按大小合并的并查集（语言：Python）"""

    def __init__(self, n: int):
        self.parent = list(range(n))   # parent[i] 指向父节点，初始各自成集
        self.size = [1] * n            # 每个集合的元素个数，用于按大小合并
        self.count = n                 # 连通分量数量，随合并递减

    def find(self, x: int) -> int:
        # 迭代版路径压缩：第一趟找到根，第二趟沿途节点全部直挂根
        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, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:                   # 已在同一集合，无需合并
            return False
        # 小树挂到大树下，控制树高增长
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1                # 每成功合并一次，分量数减一
        return True

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

应用一：统计省份数量（连通分量计数）。n 个城市、邻接矩阵表示是否相连，求省份总数——把每对相连的城市 union 起来，最后读分量数即可：

def find_circle_num(is_connected: list[list[int]]) -> int:
    n = len(is_connected)
    uf = UnionFind(n)
    for i in range(n):
        # 邻接矩阵对称，只扫上三角即可覆盖所有边
        for j in range(i + 1, n):
            if is_connected[i][j] == 1:
                uf.union(i, j)
    return uf.count

应用二：冗余连接（找成环的那条边）。一棵树多加了一条边变成有环图，找出这条多余的边——逐条处理边，若两个端点已经连通，说明当前边就是成环边：

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    uf = UnionFind(len(edges) + 1)     # 节点从 1 开始编号，多开一位
    for u, v in edges:
        # 端点已连通还继续加边，这条边必然成环
        if not uf.union(u, v):
            return [u, v]
    return []

复杂度推导：初始化 O(n)；单次 find 最多做两趟「向上走 + 途中拍平」，均摊 O(α(n))；union 内部是两次 find 加常数工作，同阶。m 次混合操作总代价 O(m·α(n))，空间 O(n)。边界条件要注意：节点编号若不从 0 开始（如上例从 1 开始），初始化容量要多开一位；孤立元素天然各自成集，无需特殊处理；重复 union 同一对元素会直接返回 False，天然幂等。

避坑总结

1. find 别写递归版。Python 默认递归深度约 1000，一顺手写成递归 find，遇到退化长链或大数据就直接 RecursionError；迭代两趟写法既能拍平又不怕爆栈。
2. 判连通必须用 find(a) == find(b)。直接比较 parent[a] 和 parent[b] 是错的——两个中间节点的父节点可能恰好相同，也可能都是别的中间节点；只有「根的 parent 指向自己」这一条性质可靠。
3. 连通分量数要在所有合并结束后再读。union 过程中的 count 只是中间状态，边还没处理完就读它，结果必然偏大。
4. 合并方向不能放飞。路径压缩能兜底大部分退化，但「永远让编号小的当根」这类随意的合并规则，在特定输入序列下依然能构造出最坏 O(n²)；配上按大小/按秩合并才是理论保证。
5. 变形按需上，别过度设计。带权并查集（维护节点间相对关系）、种类并查集（扩域拆点）都是基础版的延伸，先把基础版的压缩与合并吃透，遇到「关系传递」类题目再升级，避免一上来就堆复杂度。

写在最后

并查集是「代码量与威力比」最高的一种数据结构：三十行实现，换来近乎常数的动态连通性判定。它真正难的不是写出来，而是理解两处优化为什么互相成就——路径压缩让「走过的路」变成「铺好的路」，按秩合并让「树长高的速度」被规模翻倍锁死。把这两条推导自己走一遍，再去刷动态连通性的变形题，会发现它们不过是同一套骨架上的不同挂载。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。