并查集图解：路径压缩和按秩合并，各自挡住了哪一种最坏情况

并查集（Disjoint Set Union，DSU）只回答两个问题：两个元素是不是在同一组；把两组并成一组。它用一个 parent 数组表示一片森林，每棵树是一组，树根是这一组的代表。find(x) 沿着 parent 往上走到根，unite(a, b) 把一棵树的根挂到另一棵树的根下面。

几乎所有教程都会说「要加路径压缩和按秩合并，复杂度接近常数」。这篇不重复那个结论的证明，而是把四种组合在同样的输入上跑一遍，看每个优化具体挡住了什么。

朴素并查集的最坏情况是树退化成一条链，此时一次 find 要走过链上的所有节点。路径压缩和按秩合并都能改善这一点，但作用的时机不同：前者在查询时把走过的路径压平，后者在合并时就避免树长高。下文用同样的输入分别测量四种组合，看清两者各自挡住的是哪一种最坏情况。

四种组合，两种输入

实验用 10 万个点，统计 find 沿 parent 往上跳的总步数。四种实现：

• naive：unite 总是把 a 的根挂到 b 的根下，find 不改任何东西；
• compress：只加路径压缩，find 找到根以后，把路上每个点直接挂到根下；
• rank：只加按秩合并，矮的树挂到高的树下，find 不改；
• both：两者都加。

两种输入：一种是 unite(0,1)、unite(1,2)……依次连成一条链；另一种是 10 万次随机点对合并。合并完之后，再对每个点调一次 find。g++ 14.2 和 clang++ 19.1 的结果逐字一致：

输入一：unite(i, i+1)，i 从 0 到 99998

输入二：10 万次随机合并

naive 在链状输入上走了将近 50 亿步，这一个程序在本机跑了半分钟以上，其余三种加起来不到一秒。

输入一为什么让 naive 和 compress 都长成一条链

unite(i, i+1) 时，i 的根就是 i 自己（前一步它刚被当作 b 接上，还是根），i+1 也是根。naive 把 i 挂到 i+1 下面。连完之后：

0 → 1 → 2 → 3 → … → 99999（根）

合并阶段一步都没跳，因为每次 find 的参数都已经是根。代价全部推迟到了查询：find(0) 要走 99999 步，find(1) 走 99998 步，总和约 n²/2，即 50 亿。

compress 的合并过程和 naive 一模一样，所以合并后树高也是 99999。区别在第一次 find(0)：它走完 99999 步找到根，然后把路上所有点都直接挂到根下，树一下子被拍平。之后每个点只要 1 步。总步数约 2n。

rank 根本不会长出链。第一次合并后 0 的秩变成 1，此后每个新点都是秩 0 的单点树，被挂到 0 下面。结果是一棵以 0 为根的星形树，高度 1。

所以在这份输入上，压缩是事后补救：第一次查询付出一次 O(n) 的代价，之后变平；按秩合并是事前预防：树从来没有变高过。

一次合并的逐步状态

用 6 个点、5 条边看 both 版本的 parent 数组怎么变。下面是 Playground 程序的实际输出整理，下标 1 到 6：

画成森林：

      1          5
     / \         |
    2   3        6
        |
        4

注意 4 仍然指向 3，没有直接指向根 1。路径压缩是惰性的，只压缩被 find 走过的路。unite(2,4) 那一步调用了 find(4)，那时 3 还是根，4 到根只有一步，没什么可压。unite(1,3) 查的是 1 和 3，也没经过 4。下一次有人调 find(4)，它才会被挂到 1 下面。

秩为什么不等于高度

按秩合并里的「秩」是高度的上界，不是精确高度。路径压缩会让树变矮，但没人去更新秩，因为那样要遍历整棵树。好在算法只需要一个上界：只要保证秩小的挂到秩大的下面，秩为 k 的树至少有 2ᵏ 个点，所以秩不超过 log₂ n。

不想维护秩，也可以按大小合并：记录每棵树的点数，小的挂到大的下面。效果相同，而且点数在很多题里本来就要用（比如「求最大连通块的大小」）。

在这里跑

程序读 n、m 和 m 条边，用两种优化都加的并查集处理。点数不超过 12 时，每条边之后打印一次 parent 数组；遇到两端已经连通的边，就报告它「closes a cycle」，这就是 LeetCode 684「冗余连接」要找的边。

g++ 14.2 和 clang++ 19.1 都以 -O2 -Wall -Wextra 编译无警告，默认 stdin 下输出一致：

after 1-2: parent = 1 1 3 4 5 6  components=5
after 3-4: parent = 1 1 3 3 5 6  components=4
after 2-4: parent = 1 1 1 3 5 6  components=3
after 5-6: parent = 1 1 1 3 5 5  components=2
edge 1-3 closes a cycle
after 1-3: parent = 1 1 1 3 5 5  components=2
components=2

点编号越界时程序报错退出，例如 3 1 配一条 1 5，stderr 是 Edge 1: expected two nodes in 1..3.，退出码 1。

find 写成两个 while 循环而不是常见的一行递归 return parent[x] == x ? x : parent[x] = find(parent[x]);，原因是递归版在压缩之前要先沿链走到底，第一次查询一条 10 万长的链时，递归深度就是 10 万。上面的表里 compress 在输入一上恰好就是这个情形。

做实验时踩到的一个坑

随机输入那组数据，若写成 d.unite(rng() % n, rng() % n)，g++ 和 clang++ 的 rng 实现不同，同一种子下树高、步数会对不上——对拍时必须固定生成器，不能混用库自带的随机引擎假设。

原因是 C++ 没有规定函数实参的求值顺序。两次 rng() 谁先调用，由编译器决定：本机 g++ 先算右边的实参，clang++ 先算左边的，于是两边拿到的点对是 (b, a) 和 (a, b)。naive 版本对参数顺序敏感（总把 a 的根挂到 b 下），结果就不同了。改成先把两个随机数分别存进变量再调用，两个编译器的输出逐字节一致，上面的表就是改过之后的数据。

凡是实参里有副作用（读输入、取随机数、自增），都应该先拆成单独的语句。

它在其他问题里的位置

点的编号很大（比如到 10⁹）但实际只用到几万个时，先做 坐标压缩，把编号映射成 0 到 k-1，再建并查集。

离线处理是另一种常见搭配。题目问「删掉若干条边以后各点是否连通」，并查集不支持删边，就把操作倒过来：从全部删完的状态开始，倒着把边加回去。这种「换个方向让问题只剩加法」的想法，和 前缀和 把区间查询变成两次前缀相减，是同一类转换：找到一个只需要单向累积的表示。

Kruskal 最小生成树是并查集最经典的用法：边按权排序，依次尝试 unite，返回 false 的边跳过。排序那一步的比较函数，也要满足 严格弱序。

并查集也常用来把记录按共享字段分组，例如两条记录只要用了同一个邮箱就视为同一个用户，这正是 LeetCode 721（账户合并）。做法是给每条记录一个编号，用哈希表把每个邮箱映射到第一次出现它的记录编号，之后再遇到同一个邮箱就把两条记录 unite，最后按 find 的结果分组输出。哈希表这一步的作用，和前面提到的坐标压缩相同。