树系列第 18 篇：并查集——森林与连通性

本文是“树系列”的第 18 篇。第 1、2 篇我们认识了树和森林，第 4 篇认识了双亲表示法；今天要讲的主角，是把“一堆小树”真正派上用场的数据结构——并查集（Union-Find）。它只做两件事：把两个圈子合并成一个，以及回答“你和我在不在同一个圈子”。别看它简单，社交网络的“好友同组”判断、无向图的连通分量统计、Kruskal 最小生成树算法，背后全是它的身影。本篇会从朋友圈问题讲起，先看朴素标记为什么不行，再引出“每个集合一棵树”的森林直觉，然后一步步实现 find 与 union，讨论路径压缩和按秩合并这两个“点石成金”的优化，最后用复杂度直觉、完整走查、经典应用和自测题收尾。

0 先回顾：树、森林与双亲表示法

0.1 从第 1、2 篇捡回术语

第 1 篇我们回答了“为什么需要树”：数组和链表只能表达线性的前后关系，而现实里的组织关系往往是层次化的——文件夹套文件夹、公司管部门、目录挂子目录。树正是表达“一个父亲可以有多个孩子”这种关系的结构。

第 2 篇我们把这些术语一个个捡了回来：**节点（node）**是树里的基本单位；**边（edge）**连接两个节点；**根（root）**是唯一没有父亲的节点；**叶子（leaf）是没有孩子的节点；从根出发沿着边一层层往下走，每个节点可以有若干孩子；有同一个父亲的节点互为兄弟。我们还定义了两个重要的量：节点的深度（depth）是从根到它的边数，整棵树的高度（height）**是根到最远叶子的边数。这些词本篇都会用到，尤其是“高度”和“深度”——在按秩合并那一节，它们会从术语变成算法的核心指标。

最重要的一个概念是子树（subtree）：把一个节点连同它所有的后代一起剪下来，得到的仍然是一棵树。树的递归定义就建立在子树上：一棵树要么是空树，要么由一个根节点加上若干棵互不相交的子树组成。这个递归的视角贯穿整个树系列，并查集虽然没有显式地写出建树代码，但它的 find 操作天然适合用递归描述——沿着 parent 一路向上，本质上就是在遍历“从当前节点到根”的这条唯一路径。

0.2 森林：多棵树的集合

第 2 篇还介绍过一个相对冷门的词——森林（forest）。森林的定义只有一句话：若干棵互不相交的树组成的集合。听起来它只是“树的复数形式”，但实际上它比“树”更贴近很多真实系统的常态：一个目录树可以按子树拆成几部分分别讨论，一个公司的组织架构图可以按事业部拆成几棵独立的树，一个社交平台上的用户关系网络，也可以被划分成许多互不相连的“圈子”。

为什么本篇特别需要森林？因为并查集在任意时刻维护的，正是一个动态变化的森林：一开始每个元素都是孤零零的一棵“单节点树”，整个森林里有 n 棵独立的树；随着合并操作的发生，一些树被连在一起，森林里的树越来越少；当所有元素最终都在同一个集合里时，森林就变成了一棵完整的树。并查集的“并”，就是森林里两棵树的合并；“查”，就是在一棵树里沿着指针找根。把并查集理解成“一片会自己生长的森林”，后面所有的操作和优化都会变得顺理成章。

上面这张图就是一片森林：集合 A 是一棵 3 节点的树，根是 1；集合 B 是一棵 2 节点的树，根是 4；集合 C 只有孤零零的一个节点 6，它自己既是根也是叶子。三棵树之间没有任何边相连，这正是“互不相交”的含义。如果合并集合 A 和集合 B，森林里就只剩下两棵树；再合并一次，就只剩一棵树。这个“树的数量从 n 递减到 1”的过程，就是并查集的生命史。

0.3 第 4 篇的双亲表示法重现

第 4 篇我们讲了四种树的存储方式，其中有一个“偏科严重”的方案叫双亲表示法（parent representation）：每个节点只记录“我的爸爸是谁”，用一个数组就能装下整棵树。比如 parent[2] = 5 表示“节点 2 的父亲是节点 5”，根节点的父亲可以是 -1（或者自己），表示“我没有爸爸”。

当时的结论是：双亲表示法查父亲 O(1)、沿父亲链向上追溯每步 O(1)，但查孩子必须扫描整个数组，是 O(n)。所以它平时显得很鸡肋——可它有一个完美的舞台，就是并查集。为什么？因为并查集的操作方向只有“向上”：find 要从任意节点一路向上走到根，union 要把一棵树的根挂到另一棵树的根下面，全程不需要“查孩子”。既然只需要向上的信息，那就只存向上的信息，这正是双亲表示法的哲学：别为不存在的需求付费。

上面这张图把“parent 数组”和“树”两件事叠在一起看：数组的下标代表节点编号，数组里存的值代表它爸爸的编号。节点 1 的 parent 是 -1，说明它是根；节点 0 和 2 的 parent 都是 1，说明它们是 1 的孩子；节点 3 的 parent 是 2，说明它的爸爸是 2。顺着这条链向上走：3 → 2 → 1，最终到达根 1。整棵树不需要孩子指针、不需要左兄弟右兄弟，只需要这一行 parent 数组——这就是双亲表示法最极简的形态，也是本篇全部代码的骨架。

0.4 本篇路线图

本篇的路线图如下：第 1 章讲问题本身，看朴素标记法为什么撑不住；第 2 章讲森林直觉，建立“每个集合一棵树、根就是代表”的模型；第 3 章实现 find 和 union 两个核心操作，并看清朴素实现的退化问题；第 4 章讲路径压缩；第 5 章讲按秩合并；第 6 章用反阿克曼函数给出复杂度直觉；第 7 章用一组完整操作逐步走查；第 8 章讲五个经典应用；第 9 章介绍带权并查集与可撤销并查集两个变体；第 10 章整理实现细节与常见坑；最后是复杂度速查表、自测题和下一篇预告。每一章都尽量配图，因为并查集的本质是“看树怎么长”，光靠文字容易绕晕。

1 问题：朋友圈的“合并”与“查询”

1.1 一个具体场景

假设你在运营一个社交平台，平台上有一万名用户。用户可以主动加好友，而“朋友的朋友”会慢慢形成一个个圈子：张三、李四、王五互相认识，组成一个圈子；赵六、钱七是发小，组成另一个圈子；还有成千上万用户暂时一个朋友都没有，各自孤零零地待着。

现在产品经理提出了两个需求。

需求一：合并（union）。每当两个用户加了好友，如果他们之前不在同一个圈子，就把两个圈子合并成一个。比如张三所在的圈子和李四所在的圈子，因为一条好友关系，从此变成同一个圈子。

需求二：查询（connected）。给定任意两个用户，快速回答“他们现在在不在同一个圈子里”。产品经理想要的响应时间是毫秒级，因为“你可能认识的人”这类功能需要在大规模用户之间反复做这种判断。

这两个需求合在一起，就是并查集要解决的经典问题：动态维护若干不相交集合，支持合并两个集合、查询两个元素是否在同一集合。注意“动态”两个字：集合不是一开始就分好、后面再也不变的，而是在不断合并中变化。数据结构必须实时反映每一次合并的结果，这比“静态地数一数有几个圈子”难得多。

1.2 把问题抽象一下

把“用户”换成“元素”，把“圈子”换成“集合”，问题就变成了更干净的形式。

有一组元素，编号为 0 到 n-1。初始时每个元素自成一个集合，所以共有 n 个集合。接下来会不断发生两类操作：

第一类是合并：把元素 x 所在集合和元素 y 所在集合合并成一个集合。合并之后，原来两个集合里的所有元素都属于同一个集合，这个动作会持续发生，集合的“圈子”越来越大。

第二类是查询：判断元素 x 和元素 y 是否在同一个集合里。查询不会改变任何结构，它只读不改。

我们希望无论合并以什么顺序发生、发生多少次，查询依然快。这就是并查集（union-find，也写作 disjoint set union，缩写 DSU）要解决的完整问题。它的英文名字非常直白：union 是“合并”，find 是“查找”，合起来就是“既能合并、又能查找的集合结构”。中文“并查集”三个字，正好对应它的三件事：合并、查询、集合。

1.3 朴素方案：每个人一个“所属组标记”

先别急着上树，看看最朴素的做法能不能行。最容易想到的方案是数组标记：准备一个数组 group，长度 n，group[i] 表示元素 i 属于哪个组。初始化时让 group[i] = i，也就是“每个人属于自己那个组”。

查询操作很好做：判断 group[x] 和 group[y] 是否相等即可，一步就完成，O(1)。

合并操作呢？把 x 所在组和 y 所在组合并，就要把 x 所在组的所有成员全部改成 y 的组号。麻烦来了：你并不知道 x 所在组都有哪些人。数组里只存了“每个人属于哪组”，没有存“每组有哪些人”，所以要把整个数组扫一遍，把所有 group[j] === group[x] 的人全部改掉。

上面的图演示了合并组 0 和组 1 的过程：先扫描一遍数组，找到所有组号为 0 的元素（本例中是 0、1、2 三个），再把它们逐个改成 1。扫描一遍是 O(n)，如果合并频繁发生在大集合上，这个代价会非常高。

1.4 为什么数组标记不行

数组标记的问题不是“不能做”，而是“合并一次要改一堆人”。把代价算清楚：

如果 n 个元素一开始各自成组，然后依次合并，最终合并成一个组，需要执行 n-1 次合并。朴素方案里，每次合并都要扫描整个数组，最坏情况下每次扫描 O(n)，总代价就是 O(n²)。n 是一万时，大约要执行一亿次操作；n 是一百万时，就是一万亿次。这还只是“把所有元素合并成一组”这一个最简单的合并序列，真实场景里合并与查询交错进行，代价只会更失控。

更微妙的问题在于：改一堆人的标记，改完之后还容易出错。比如组 0 和组 1 之前已经合并过，组号可能被改成了别的值，再合并时漏改、改错都是常事。数组标记方案把“合并”的代价摊给了“被合并的每个成员”，成员越多，单次合并越贵，而且这个贵是绕不开的——只要你存的是“每个人属于哪个组”这种完全扁平的标记，合并时就必须逐个更新成员。

如果把方案升级成“每个组维护一份成员名单”呢？合并时只需要把名单拼接起来，听起来好了不少，但拼接名单意味着要把小名单里的每个成员逐条搬进大名单，仍然是 O(成员数)；更麻烦的是，名单拼接后，原来的小名单地址就作废了，所有指向它的引用都要更新。本质上，“把一个集合合并进另一个集合”这件事，只要坚持“每个人都记住自己属于哪个组”，就逃不掉逐个修改成员。

1.5 换个思路：让“代表”来回答问题

那么，能不能不更新成员，也能让查询快速回答？让我们重新想想查询的本质。

问“x 和 y 在不在同一个集合”，不一定非要立刻读出“x 的组号”和“y 的组号”再比较。我们可以换一种回答方式：每个集合选出一个“代表”，判断两个元素是否同组，就看它们追根溯源之后找到的“代表”是不是同一个人。

如果“找代表”只需要沿着一条很短的链向上走几步，查询依然很快；而合并的时候，我们只需要处理两个集合的“代表”——把其中一个代表的指针指向另一个代表，其他所有成员一个都不用改。这样一来，合并的代价与集合大小无关，只与“代表之间挂一根指针”有关。这正是森林直觉的入口：每个集合变成一棵树，根就是代表。

1.6 两种方案的一张对比表

把数组标记法和“树 + 代表”方案放在一起，优劣一目了然：

对比项	数组标记法	树 + 代表（并查集）
存储内容	每个元素属于哪个组	每个元素的父亲是谁
查询	直接比组号，O(1)	两次 find 比根，接近 O(1)
合并	扫描数组改一堆人，O(n)	只改根的指针，接近 O(1)
集合大小的影响	合并代价随成员数增长	合并代价与成员数无关
需要的额外信息	无	rank/size 数组（可选）

这张表的核心差异只有一行：合并时，一个要改所有人，一个只改一个人。正是这行差异，让并查集在“合并频繁”的场景里胜出。而它付出的代价是查询从“直接读数组”变成“沿链向上走”——但经过路径压缩和按秩合并，这个代价被压到几乎可以忽略。

2 森林直觉：每个集合一棵树

2.1 根就是“代表”

现在我们把每个集合想象成一棵树：树里的每个节点是一个元素，树根是这个集合的代表（representative）。其他所有节点都是根的后代，它们通过 parent 指针一层一层指向根。

为什么要根当代表？因为根是整棵树的终点：从任何一个节点出发，沿着 parent 指针一路向上，最终都会到达根。这个“到达的终点”是唯一的，所以它可以稳定地代表整个集合。判断两个元素是否同组，就等价于判断“从 x 出发追到的根”和“从 y 出发追到的根”是不是同一个节点。

这个设计有一个极其重要的好处：查询不需要知道集合里有多少人，只需要沿着自己的祖先链向上走。x 的祖先链有多长，取决于 x 到根的距离，与集合总大小无关。如果树长得矮，查询就快；这也为后面的路径压缩和按秩合并埋下了伏笔——它们本质上都在做同一件事：让树尽量矮。

2.2 每个节点只存一个 parent

第 4 篇的双亲表示法在这里全面复活。并查集的每个节点不需要孩子列表，不需要左右指针，只需要回答一个问题：“我的爸爸是谁？”所以一个并查集就是一行数组：parent[i] 表示节点 i 的父亲。

根怎么表示？两种常见约定：一种是让根的 parent 指向自己，即 parent[root] = root；另一种是让根的 parent 为 -1。本篇代码采用“根指向自己”的约定，因为它在 find 的递归实现里最自然：当 parent[x] === x 时，说明已经到达根。

这张图是一棵典型的并查集树：根是 1，2、3、5 是 1 的孩子，4 是 2 的孩子。用 parent 数组表示就是 parent[1]=1、parent[2]=1、parent[3]=1、parent[4]=2、parent[5]=1。请注意，图中没有画出任何“孩子指针”——2 知道自己爸爸是 1，但 1 不需要知道自己有哪些孩子。整棵树的信息完全由“向上”的指针决定。

2.3 初始状态：每人一棵单节点树

初始化时，每个元素自成一个集合，也就是 n 棵只有根、没有孩子的树。代码只有一行循环：

const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
  parent[i] = i; // 自己是自己的爸爸：单节点树的根
}

这行代码的意义值得停下来想一想：它把“每个人都属于自己”这个初始状态，翻译成了“每个节点的 parent 都指向自己”。从这一刻起，森林里共有 n 棵树，每棵树只有一个节点；查询任何两个不同的元素，它们分别追到两个不同的根，所以答案都是“不同组”。随着后续 union 的发生，根之间的指针被挂上，树开始长大，森林开始缩小。

2.4 为什么不需要孩子指针

有人会问：树不是应该有孩子指针吗？第 4 篇讲链式存储时，每个节点都带着 left、right；这里为什么只有 parent？

答案在于并查集的操作方向。我们需要的全部操作只有两个：find 要“向上走到根”，union 要“把一棵树的根挂到另一棵树的根下面”。没有任何一个操作需要“从一个根向下遍历它所有的孩子”。既然不需要向下，就不存向下的信息。存了也是白存，只会浪费内存、增加维护成本。

这个“只存用得到的信息”的思想，和 BST 选链式、堆选数组是同一个逻辑：数据结构的长相，由它最频繁的操作决定。并查集最频繁的操作是“向上找根”，所以它只需要一行 parent 数组——这是全篇最值得记住的设计判断之一。接下来进入核心操作。

2.5 并查集的树和普通树的区别

细心的读者可能会问：第 2 篇说树有“根、边、孩子、叶子”，并查集的树也都有这些，那它和普通树有什么区别？区别不在结构，而在“用途和规则”。

普通树（比如二叉搜索树、文件目录树）强调有序性和可遍历性：节点之间有明确的“左/右”“前/后”关系，算法常常要递归访问整棵树。并查集的树则只强调一件事：从任意节点出发，最终到达同一个根。它的结构可以随意改变——只要根不变，parent 怎么指都行；它也不需要遍历，find 永远只走一条向上的路径。

换句话说，并查集的树是“只认祖先、不认子孙”的树：每个节点关心的只有“我的爸爸是谁”，至于自己有多少孩子、孩子叫什么名字，一概不管。理解了这层区别，就不会用“孩子指针”“遍历顺序”这些普通树的惯性思维去套并查集，学习曲线会平缓很多。

3 核心操作：find 与 union

3.1 find：沿着 parent 找根

find 的作用是：给定一个元素 x，返回它所在树的根。实现思路就是顺着 parent 指针一路向上，直到遇到“自己是自己的爸爸”的节点：

function find(x: number): number {
  while (parent[x] !== x) {
    x = parent[x];
  }
  return x;
}

用图来表达，find(4) 的路径是 4 → 2 → 1，然后停住。每一步都通过 parent 数组跳到爸爸那里，跳不动了就到了根。

图中箭头标出了 find(4) 走过的路：先到 2，再到 1。find 返回 1，说明 4 所在集合的代表是 1。请注意，find 只关心“向上”，它根本不在乎 3、5 这些兄弟节点长什么样。

3.2 为什么 find 是“查”的灵魂

find 返回的根就是集合的代表，所以判断两个元素是否同组，只需要比较它们的 find 结果：

function connected(x: number, y: number): boolean {
  return find(x) === find(y);
}

这一步把“查询是否同组”完全转化成了“两次找根 + 一次相等比较”。查询的代价取决于两次 find 各自走多长：如果树很矮，find 很快；如果树退化成一条长链，find 就可能要走上千步。所以后续所有优化，本质上都是在降低 find 的平均路径长度。换句话说，find 是所有操作的底层引擎：union 要 find，connected 要 find，一切代价都来自 find。

3.3 union：把一个根挂到另一个根

union 要做的是把两个集合合并。朴素思路：先分别找到 x 和 y 的根，然后把其中一个根的 parent 指向另一个根：

function union(x: number, y: number): void {
  const rx = find(x);
  const ry = find(y);
  if (rx === ry) return; // 已经在同一个集合，什么都不用做
  parent[ry] = rx; // 把 y 的根挂到 x 的根下面
}

注意三个细节。第一，union 的第一步必须是 find：只有拿到两个集合的根，才知道把谁挂到谁下面；第二，如果两个根相同，说明它们已经在同一个集合，直接返回，不能盲目挂指针，否则会把树挂成环；第三，挂的方向目前是任意的，我们选择“把 ry 挂到 rx 下面”，但朴素版本里这个选择没有讲究——后面按秩合并要在这一步做文章。

为什么“先 find 再挂”这么重要？因为 parent 数组里的值随时可能在变：路径压缩会把 parent[4] 从 3 改成根，按秩合并会把 parent[ry] 从 ry 改成 rx。直接读写 parent[x] 而不经过 find，拿到的可能是过期信息。把“union 内部永远先 find”当成一条纪律，写出来的代码就不会犯这类错误。

上图左边是合并前：rx 和 ry 分别是两棵树的根；右边是合并后：我们只改了一根指针——ry 的 parent 从自己变成 rx。树里其他所有节点（2、3、5）的 parent 一个都没动，这就是并查集合并“便宜”的原因：合并的代价与集合大小无关。

3.4 完整朴素实现

把上面的代码拼在一起，就是一个能跑的并查集：

class UnionFind {
  parent: number[];

  constructor(n: number) {
    this.parent = new Array(n);
    for (let i = 0; i < n; i++) this.parent[i] = i;
  }

  find(x: number): number {
    while (this.parent[x] !== x) x = this.parent[x];
    return x;
  }

  union(x: number, y: number): void {
    const rx = this.find(x);
    const ry = this.find(y);
    if (rx === ry) return;
    this.parent[ry] = rx;
  }

  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }
}

这个实现大约二十行，已经能正确回答“在不在一个圈子”了。可它有个致命弱点，下一节就讲。

3.5 朴素实现的问题：退化成长链

坏消息是：如果合并的方向一直很“倒霉”，树会退化成一条长链。

考虑这样的操作序列：union(1, 2)，把 2 挂到 1 下面；union(2, 3)，把 3 挂到 2 下面；union(3, 4)，把 4 挂到 3 下面……每次都把“新元素”挂到“当前链的末端”下面，最终会得到一条 n 个节点的链。

此时 find(n) 要从 n 一路爬到 1，走 n-1 步。如果接下来执行 m 次 find，总代价就是 O(mn)，和朴素数组标记法一样糟糕。为什么会这样？因为 union 只改了根，但根的选择完全没有考虑“哪棵树更矮”——每次都把大树挂到小树下面，树的深度就在不知不觉中一路涨上去。

上图就是退化后的树：5 个节点排成一条链。find(5) 要走 4 步，find(1) 只要 1 步。如果有一万个节点，find(10000) 要爬九千九百九十九步——这就是“树长得太深”的代价。注意，这棵树在结构上完全合法：每个节点只有一个父亲，没有环，根是 1；它只是“深得离谱”。

3.6 退化场景真的会发生吗

有人会想：谁会闲得没事按这种顺序合并？但在真实数据里，“恰好形成链”的顺序并不罕见。比如依次添加新节点并连接到“当前代表”上，或者数据本身按某种单调顺序输入，都可能让树不知不觉长高。更麻烦的是，并查集经常要处理海量操作，哪怕平均深度只有几十，上亿次 find 也会被拖垮。

所以我们必须主动控制树的高度。控制的方法有两招：路径压缩和按秩合并。它们一个从“find 的过程”入手，一个从“union 的挂法”入手，两者结合就能把复杂度压到近乎常数。

3.7 一个常见的理解误区

有人会把“树的深度”和“集合的大小”混为一谈，认为集合越大树一定越深。其实两者没有必然关系：一棵 8 个节点的满二叉树，高度只有 2；一条 8 个节点的链，高度却有 7。集合大小决定不了树高，决定树高的是合并的方式。这也是为什么“按秩合并”值得单独设计——它就是要让“越大”不等于“越深”。

3.8 find 的返回值到底代表什么

还有一个容易混淆的细节：find(x) 返回的是“根”，不是“集合”。同一个集合的所有成员调用 find，得到的返回值一定相同；不同集合的成员调用 find，返回值一定不同。这个“相同即同组”的性质，是所有基于并查集的算法正确性的地基。

正因为如此，find 的返回值可以当作“集合的编号”来用：统计连通分量个数时，把所有 find(i) 塞进一个 Set，Set 的大小就是分量数；判断两个点是否连通时，比较两次 find 的结果即可。整个数据结构里，只有根节点“代表”集合，其他节点只是根的后代，它们自己不直接拥有编号——这是“代表制”和“全员标记制”最大的区别。

4 路径压缩：find 时顺手把路修平

4.1 动机：走过的路别白走

观察朴素 find 的一个现象：调用 find(5) 时，我们沿着 5 → 4 → 3 → 2 → 1 走了一遍，知道了 5 的根是 1。但这次行走除了返回根，什么都没留下——下次再 find(5)，还要原路再走一遍。

更浪费的是：在这次行走中，我们不仅知道了 5 的根是 1，还知道了 4、3、2 的根也是 1。这几个节点明明已经“亲眼看到”根在哪，却什么都不记得，下次各自还要重新爬一遍。如果每个节点都能把“我的根是 1”这件事记下来，之后的 find 就只需要一步。

路径压缩（path compression）就是这个想法：find 在向上走的过程中，把沿途经过的每个节点的 parent 直接改成根。走一次 5 → 4 → 3 → 2 → 1，回来时顺手把 5、4、3、2 的 parent 全部改成 1。下次再 find 任何一个，都是“一步到根”。

4.2 压缩前后的对比

压缩前，树是下面左图的样子，find(5) 要爬 4 步；压缩后，树变成右图：5、4、3、2 全部直接挂在 1 下面，整棵树的高度变成 1，find(5) 只需要 1 步。

请注意：路径压缩不是单独做一次“整形”操作，而是 find 的副产品——find 本来就要走这条路径，压缩只是让它在返回时把路修平。所以在代码层面，压缩几乎是“免费的”：不增加额外操作次数，只是把沿途的 parent 赋值换成根。

4.3 递归写法与迭代写法

路径压缩的递归写法非常优雅：

find(x: number): number {
  if (this.parent[x] !== x) {
    this.parent[x] = this.find(this.parent[x]); // 递归时顺手压缩
  }
  return this.parent[x];
}

这里的关键是递归的“回程”：先递归地找到根，然后在返回时，把当前节点的 parent 直接赋给根。parent[x] 先被用于递归，递归返回后再被改成根。这样一路回程，每个节点都指向根。

如果担心递归深度（比如树特别深，或者运行环境对调用栈有严格限制），可以写迭代版：先走一遍找到根，再走一遍把沿途节点全部指向根。

find(x: number): number {
  let root = x;
  while (this.parent[root] !== root) root = this.parent[root];
  while (this.parent[x] !== x) {
    const next = this.parent[x];
    this.parent[x] = root;
    x = next;
  }
  return root;
}

两遍循环：第一遍找根，第二遍修路。注意第二遍循环结束时，x 已经走到根，且根指向自己，所以循环自然终止。

4.4 为什么“几乎免费”却有巨大收益

路径压缩的成本怎么算？find 本身要走的路径长度就是它原本的代价，压缩并没有增加额外的一轮完整遍历——只是在回程中多做一次赋值。严格来说，第一次 find 一个深节点时，代价仍然是 O(深度)，但这一次行走把整条路径都压平了，之后这条路径上所有节点的 find 都是 O(1)。也就是说：压缩花掉的“钱”，就是这一次本来就要花的“路费”；但它买来的收益，是这条路今后永远通畅。

把这种收益摊到整个操作序列上，就出现了惊人的效果：即使没有按秩合并，只靠路径压缩，m 次操作的总复杂度也是接近线性的。再加上按秩合并，就能达到反阿克曼函数的级别——这个我们第 6 章再细说。

4.5 路径压缩的一个变体：折半压缩

除了“全部压缩”之外，还有一类更轻量的写法叫折半压缩（path halving）：在 find 的循环里，每走一步就把当前节点直接挂到它的“爷爷”下面，然后从爷爷继续走。

find(x: number): number {
  while (this.parent[x] !== x) {
    this.parent[x] = this.parent[this.parent[x]]; // 挂到爷爷
    x = this.parent[x];
  }
  return x;
}

折半压缩每次把节点提升一代，虽然没有“一步到位”那么彻底，但它的好处是代码极短、不需要两遍遍历，而且同样能显著压低树的深度。很多教材把完整压缩写成“路径压缩”，把折半压缩当成一种变体；工程上两种都可以，本文后续统一使用完整压缩。

4.6 一个容易误解的点

路径压缩会不会破坏并查集的正确性？不会。并查集的树不是“有严格形状要求的树”，它只在乎一件事：同一个集合里的所有节点，最终都能追到同一个根。把 parent 从“爷爷”改成“老祖宗”，没有改变“最终到达的根”，只是缩短了路径。所以路径压缩是安全的结构变换，它甚至不需要知道树长什么样，只需要在 find 时顺手做。

另外要注意：路径压缩后，树的真实高度变小了，但按深度合并所需的“秩”并不会跟着改。这引出了按秩合并的一个重要细节——我们下一章会专门讨论 rank 到底该怎么定义。

4.7 路径压缩的正确性直觉

为什么把 parent 改成根不会“改坏”集合关系？因为并查集的树不是家谱，它没有“辈分必须正确”的约束；它唯一的约束是“同一个集合的节点最终追到同一个根”。把节点 x 的 parent 从“它的爸爸”改成“它的老祖宗”，改变的只是 x 向上走的路程长短，没有改变这条路的终点。

这一点可以推广成更一般的结论：只要 parent 指针始终指向“原集合内部”的某个节点，并且根始终不变，并查集的性质就不会被破坏。路径压缩、折半压缩都满足这个条件，所以它们无论什么时候触发、触发多少次，都是安全的。做题时如果担心压缩影响结果，请记住：压缩改变的只是“怎么走”，从不改变“走到哪”。

4.8 压缩次数与性能的直观实验

如果想知道路径压缩到底有多“神”，可以做个简单实验：先用一万次“倒霉”的 union 造出一万节点的长链，然后连续执行一万次 find(9999)。朴素实现的每次 find 都要从 9999 爬到 0，总共约五千万次指针跳跃；而带路径压缩的实现里，第一次 find 就花了全部力气把整条链压平，后面九千九百九十九次 find 全部一步到位，总跳跃次数只有两万左右。同样的操作序列，时间差距是上千倍——这就是“一次的代价换永久通畅”的最直观证据。

5 按秩合并：总是矮树挂高树

5.1 路径压缩解决不了的问题

路径压缩让“走过的路变短”，但它治标不治本：如果 union 总是把高树挂到矮树下面，树的深度仍可能不断增长，find 第一次访问深节点时还是要爬很长的路。

举个例子：一棵高 10 的树 A，一棵高 1 的树 B。朴素 union 如果选择把 A 的根挂到 B 的根下面，A 的所有节点深度都会加 1，新树的高度变成 11；如果反过来，把 B 挂到 A 下面，B 的节点深度变成 2，新树的高度还是 10。显然第二种挂法更聪明：把矮树挂到高树下面，树的高度不会增加。

这就是按秩合并（union by rank）的出发点：在 union 时不是随便挑一个根当新根，而是有意识地选择——让矮树的根挂到高树的根下面。这样每一次合并，树的高度要么不变，要么只加 1，而且只有在两棵树一样高时才会加 1。

5.2 按大小合并与按深度合并

“矮树挂高树”具体怎么判断谁矮？有两种常用度量。

第一种是按大小（size）合并：每个根记录自己这棵树有多少个节点，合并时总是把节点少的树挂到节点多的树下面。为什么按大小也有效？因为一棵树的高度不超过它的节点数，把“小树挂大树”保证了任何节点的深度最多是对数级别——直观上，每当一个节点的深度增加 1，它所在树的节点数至少翻一倍，所以深度最多是 log n。

第二种是按深度（rank）合并，也就是最经典的“按秩”做法：每个根记录自己这棵树当前的高度（并查集里习惯叫 rank，秩），合并时总是把秩小的树挂到秩大的树下面；只有两棵树秩相等时，被挂的那棵的根要加 1。如果使用了路径压缩，树的真实高度会变小，但 rank 可以保留“合并历史”的估计值，依然能给出正确的界。

图中左边是两棵树：A 高 3，B 高 1；右边是按秩合并的结果：B 的根挂到 A 的根下面，新树高度仍是 3。如果挂反，A 的根挂到 B 下面，A 的每个节点深度加 1，新树高度会变成 4。两个选择只差一根指针的方向，树的高度却差了一层，这就是“排序挂法”的价值。

5.3 按秩合并的实现

按秩合并需要额外一个数组 rank（或 size），初始全为 0（单节点树高度为 0）。union 时先 find 两个根，然后比较秩：

class UnionFind {
  parent: number[];
  rank: number[];

  constructor(n: number) {
    this.parent = new Array(n);
    this.rank = new Array(n).fill(0);
    for (let i = 0; i < n; i++) this.parent[i] = i;
  }

  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }

  union(x: number, y: number): void {
    let rx = this.find(x);
    let ry = this.find(y);
    if (rx === ry) return;
    if (this.rank[rx] < this.rank[ry]) {
      [rx, ry] = [ry, rx]; // 保证 rx 是秩较大的根
    }
    this.parent[ry] = rx; // 矮树挂高树
    if (this.rank[rx] === this.rank[ry]) {
      this.rank[rx]++; // 两棵树一样高，挂完高度加 1
    }
  }
}

注意交换技巧：先通过一次解构赋值把 rx 和 ry 换成“秩大的在前”，然后统一执行 parent[ry] = rx，代码就只有一个挂法分支。只有两棵树的秩相等时，新树的高度才增加 1，所以 rank 的更新也只有一个分支。

5.4 和路径压缩的组合

两个优化能不能同时用？能，而且这是标准做法。路径压缩负责“把走过的路压平”，按秩合并负责“让新长出来的树尽量矮”。它们互不冲突：按秩合并只在 union 时决定挂的方向；路径压缩只在 find 时修改 parent。唯一的联动是：路径压缩后树的真实深度变小了，但 rank 不跟着改——这不会破坏正确性，因为 rank 现在只是一个“上界估计”，两个优化合起来依然满足复杂度分析所需的性质。

为什么 rank 不更新反而更好？因为如果每次压缩都去重新计算真实深度，find 就不只是“顺手修路”了，还要额外维护一套深度信息，代价变大；而保留原来的 rank 依然能保证“深度不超过 rank”的界，复杂度结论不受影响。这也是并查集实现里最常见的一个坑：路径压缩和按秩合并一起用时，rank 绝不减、也不需要减。

5.5 直觉：为什么树矮了，一切就快了

把两个优化的效果合起来看：按秩合并保证任何树的高度不超过 O(log n)——注意这是在没有路径压缩时的结论；路径压缩又在实际操作中把树压得更平。两者叠加之后，find 的平均代价下降到“几乎常数”，后面第 6 章给精确的直觉。

如果只实现一个，选哪个？工程上通常两个都做，因为代码量只多三行；如果非要二选一，路径压缩的实现更简单、收益更直接，但最坏情况仍然可能较慢；按秩合并单独使用，能保证最坏 O(log n) 的 find，但平均表现不如两者组合。竞赛和面试的标准答案都是“两个都写”。

5.6 按大小合并的写法

如果题目需要随时知道集合大小（比如“合并后输出最大集合大小”），按大小合并更顺手。它和按秩合并只差一个数组：

class UnionFindBySize {
  parent: number[];
  size: number[]; // 只有根上的 size 有意义

  constructor(n: number) {
    this.parent = new Array(n);
    this.size = new Array(n).fill(1);
    for (let i = 0; i < n; i++) this.parent[i] = i;
  }

  union(x: number, y: number): boolean {
    let rx = this.find(x);
    let ry = this.find(y);
    if (rx === ry) return false;
    if (this.size[rx] < this.size[ry]) [rx, ry] = [ry, rx];
    this.parent[ry] = rx;
    this.size[rx] += this.size[ry];
    return true;
  }
}

注意 size 只在根上维护：合并时把被挂那棵树的 size 加到大根上，其他节点的 size 不需要更新，因为只有根会参与比较。两种“按秩”的本质相同：用一棵树的一部分信息（节点数或高度）来决定“谁当根”，从而控制树高。

6 复杂度：反阿克曼函数到底有多慢

6.1 结论先行

同时使用路径压缩和按秩合并的并查集，m 次操作（union 或 find）的总时间复杂度是 O(m α(n))，其中 α 是反阿克曼函数（inverse Ackermann function），n 是元素个数。单次操作的均摊复杂度就是 O(α(n))。

“均摊”的意思是：单次操作偶尔可能慢一点（比如第一次 find 一条很深的路径），但把 m 次操作平均起来，每次的代价都落在 α(n) 这个级别。算法竞赛、面试、工程里说的“并查集是 O(α(n)) 的”，指的就是这个均摊结果。

6.2 α(n) 的直觉：增长慢到像常数

α(n) 是什么？它由阿克曼函数反推而来，但理解它不需要背任何公式，只需要一个直觉：阿克曼函数增长得极快，所以它的反函数 α(n) 增长得极慢。

给几个具体数值感受一下：α(10³) 大约是 2 到 3，α(10⁶) 大约还是 3 到 4，α(10⁹) 大约是 4，α(10¹⁸) 也还不到 5。也就是说，就算元素个数是宇宙中原子数量级别，α(n) 也不超过 5 左右。在你能想象的任何实际输入规模下，α(n) 都像一个很小的常数。

所以复杂度 O(m α(n)) 在工程上几乎就等于 O(m)：总时间与操作次数成正比，每个操作平均只需要“几步”。这正是并查集能处理千万级元素、上亿次操作的原因。你不需要算出 α 的精确值，只需要记住“它慢到像常数，而且比 log 还慢得多”。

6.3 各种情况下的复杂度

把优化组合和复杂度对照起来看，结论更有层次：

• 朴素实现（无优化）：find 最坏 O(n)，m 次操作最坏 O(mn)；
• 只按秩合并（无路径压缩）：每个 find 最坏 O(log n)，m 次操作最坏 O(m log n)；
• 只路径压缩（无按秩合并）：m 次操作的总复杂度在 O((m+n) log n) 级别；
• 路径压缩 + 按秩合并：m 次操作 O(m α(n))。

这些结论不需要背，只需要记住一个方向：优化的本质是控制树的高度。树越矮，find 越便宜；两个优化一个管“已经存在的路”，一个管“新挂出来的路”，双管齐下才拿到最优的界。

6.4 为什么说“均摊”而不是“最坏”

严格来说，路径压缩 + 按秩合并的并查集，单次 find 的最坏时间仍然是 O(log n) 甚至更高——因为总有一些“第一次访问深节点”的操作比较贵。但“均摊”告诉我们：这些贵操作不会一直出现，每一次贵操作都伴随大量便宜的后续操作，把总账摊平之后，平均每个操作就是 O(α(n))。

理解均摊的一个朴素类比：一家餐厅偶尔会办一场婚宴，单场成本很高；但把一年所有宴会平均起来，每场宴会的成本其实不高。并查集的路径压缩就是这样——第一次 find 一个深节点相当于办婚宴，之后这条路径上的节点全部变平，相当于后续宴会都办成了快餐。

6.6 从 log 到 α：一次复杂度“降维”

二叉搜索树的核心操作是 O(log n)，已经是很多教材里的“快”；并查集进一步把单次操作压到 O(α(n))，而 α(n) 比 log n 还要慢上几个数量级。直观地说，log n 是说“数据量翻一倍，操作数加一”；α(n) 则是说“数据量指数地翻倍又翻倍，操作数才加一”。

一个对比可以帮助建立感觉：n 取十亿时，log₂ n 大约是 30，α(n) 大约是 4。同样是十亿个元素，BST 的查找最坏要走三十步，而并查集的 find 平均只要四步左右。在“百万级元素、上亿次操作”的刷题场景里，这个差距意味着：BST 方案可能因为常数而超时，并查集方案则几乎永远游刃有余。

但请务必记住一个前提：这个惊人的复杂度属于“路径压缩 + 按秩合并”的组合。只写 find 不写 union 的优化，或者只优化一半，得到的都是 log 级别的界。面试时写并查集，两个优化一起上，是既安全又专业的习惯。

6.7 关于复杂度的三个常见误解

第一个误解：“O(α(n)) 就是 O(1)。” 严格说不等，α(n) 虽然小，但它确实随 n 增长；只是在所有实际输入规模下，它都不会超过 5 左右。把它当成“工程上的常数”没问题，但考试和面试时说成 O(1) 会被挑毛病。

第二个误解：“并查集所有操作都是最坏 O(α(n))。” 不对。单次 find 的最坏情况仍然可以是 O(log n) 甚至更差，O(α(n)) 是均摊结果。题目问“最坏复杂度”时，标准答案是“均摊 O(α(n))，单次最坏 O(log n) 级别”。

第三个误解：“优化越多越好，路径压缩应该每次 find 都触发。” 路径压缩不是目标，而是副产品；它只在 find 走过长路径时发生。刻意为了压缩而多次 find、或者在 union 里额外加一次 find，只会增加常数开销，没有任何收益。优化的正确姿势是“顺其自然”：find 按标准写法实现，压缩自动发生。

6.5 为什么本篇不做严格证明

严格的复杂度证明要动用“摊还分析”里的势能法（potential method），还要把 rank 分层、把路径压缩的收益分类计数，写下来超过十页纸，而且对理解和写代码几乎没有任何帮助。本系列的目标是“能设计、能分析、能上手”，所以我们只保留两个必知的结论：第一，α(n) 慢到像常数；第二，两个优化缺一不可地组合时，才能拿到这个界。想深入的同学可以去看《算法导论》并查集一章，那里有完整的证明；本篇更关心的是：怎么把并查集写对、怎么用它解决真实问题。

7 完整示例：一组操作逐步走查

7.1 场景设定

理论讲了不少，现在用一组真实操作把并查集从头到尾“跑”一遍。假设有 6 个元素，编号 0 到 5。初始时各自成组。下面按顺序执行 7 次操作：

操作 1：union(0, 1)

操作 2：union(2, 3)

操作 3：union(0, 3)

操作 4：find(1)

操作 5：union(1, 4)

操作 6：find(4)

操作 7：union(5, 2)

我们使用带路径压缩和按秩合并的标准实现，合并方向按 rank 决定。走查时盯住三样东西：每次 find 走的路、每次 union 挂的方向、parent 数组的变化。

7.2 一步一步推

初始时 parent = [0, 1, 2, 3, 4, 5]，rank 全为 0。

操作 1：union(0, 1)。 find(0) 返回 0，find(1) 返回 1，两个根不同。rank[0] = rank[1] = 0，两棵树一样高，按“相等则前一个当根”的约定，把 1 挂到 0 下面，rank[0] 变成 1。此时 parent = [0, 0, 2, 3, 4, 5]，森林里有两棵“双节点树”（0-1 和 2-3 还没有出现，2-3 在下一步才合并）。

操作 2：union(2, 3)。 同理，find(2) 返回 2，find(3) 返回 3，两棵树一样高，把 3 挂到 2 下面，rank[2] 变成 1。此时 parent = [0, 0, 2, 2, 4, 5]，森林里有树 {0,1}、树 {2,3}、单节点树 {4}、单节点树 {5}。

操作 3：union(0, 3)。 find(0) 返回 0，find(3) 从 3 走到 2，返回 2。比较 rank[0] 和 rank[2]：都是 1，一样高，所以把 2 挂到 0 下面，rank[0] 变成 2。此时 parent = [0, 0, 0, 2, 4, 5]。注意 parent[3] 仍然是 2，没有被直接改成 0——3 还是 2 的孩子，只是 2 现在变成了 0 的孩子。从 3 出发找根要多走一步：3 → 2 → 0。

操作 4：find(1)。 1 的 parent 是 0，0 的 parent 是 0，一步到根，返回 0。路径长度只有 1，因为 1 本来就是根的孩子。

操作 5：union(1, 4)。 find(1) 返回 0，find(4) 返回 4。rank[0] = 2 大于 rank[4] = 0，所以把 4 挂到 0 下面，rank 不变。此时 parent = [0, 0, 0, 2, 0, 5]，集合 {0,1,2,3,4} 已经是一棵树，只有 5 还孤零零的。

操作 6：find(4)。 4 的 parent 是 0，一步到根，返回 0。这次 find 没有触发压缩（本来就已经是根的直接孩子），但它的意义在于验证：4 和 0 同组。

操作 7：union(5, 2)。 find(5) 返回 5，find(2) 返回 0（路径 2 → 0）。rank[5] = 0 小于 rank[0] = 2，所以把 5 挂到 0 下面，rank 不变。最终 parent = [0, 0, 0, 2, 0, 0]。

7.3 三个关键状态的图

下面把三个关键状态画成图：操作 3 之后、操作 5 之后、最终状态。请对比每张图里的树长什么样，再看 parent 数组怎么对应。

三张图连起来看，就是一个“森林收缩”的过程：第一张图里还有 4 棵独立的树，第二张图里剩 2 棵，第三张图里只剩 1 棵。整个过程里，任何节点都没有改变过“最终属于哪个集合”，变的只是树的挂法。

7.4 走查表格

操作	find 路径	合并方向	parent 数组
初始	—	—	[0, 1, 2, 3, 4, 5]
union(0,1)	0 / 1	1 挂 0	[0, 0, 2, 3, 4, 5]
union(2,3)	2 / 3	3 挂 2	[0, 0, 2, 2, 4, 5]
union(0,3)	0 / 2	2 挂 0	[0, 0, 0, 2, 4, 5]
find(1)	1 → 0	—	[0, 0, 0, 2, 4, 5]
union(1,4)	0 / 4	4 挂 0	[0, 0, 0, 2, 0, 5]
find(4)	4 → 0	—	[0, 0, 0, 2, 0, 5]
union(5,2)	5 / 0	5 挂 0	[0, 0, 0, 2, 0, 0]

表格里每一行的 parent 数组都只比上一行多改一个位置（或者没改）。七次操作，parent 数组一共只被修改了六次——每一次修改都对应一次“根之间的合并”，没有任何一次是“遍历成员逐个改”。

7.5 从走查里读出什么

这段走查展示了并查集的三条铁律。

第一，只有根之间的 parent 会变化。每次合并最多改一个数组元素；成员本身从不被修改。对比第 1 章朴素标记法“合并一次要改一组人”，这里的优势一目了然。

第二，find 会随着树变矮越来越快。越到后面，多数节点一步就到根；即便 3 需要走 3 → 2 → 0 两步，也只是因为它在树中间。如果某次 find 恰好经过一条长路径，路径压缩会把整条路压平，之后大家集体变快。

第三，按秩合并让树始终“胖而不高”。7 次操作后，6 个节点都在一棵高 2 的树里，没有任何一个节点的 find 需要走超过 2 步。这正是“树越高越危险，树越矮越安全”的直观证据。

7.6 如果方向不讲究会怎样

让我们把操作 3 换成“把 0 挂到 2 下面”的随机方向，其他操作照旧。操作 3 之后，0 的 parent 变成 2，树变成 2 是根：0 和 1 都是 2 的子树。操作 5 的 union(1, 4) 里，find(1) 要走 1 → 0 → 2 两步；如果树的规模再大一些、这种“反向挂”再多几次，链就会越长。虽然路径压缩会救场，但“随机挂”会让压缩前的路径明显变长。按秩合并的意义，就是让“救场”的次数尽量少。

7.7 一次真正触发压缩的 find

上面的走查里，没有任何一次 find 碰到过“长路径”，所以路径压缩一直没有出场。现在补一个专门触发压缩的例子，看清它到底做了什么。

假设当前 parent = [0, 0, 2, 2, 3, 4]，也就是说树的结构是：0 是根，1 是 0 的孩子；2 是根，3 是 2 的孩子，4 是 3 的孩子，5 是 4 的孩子。此时执行 find(5)，路径是 5 → 4 → 3 → 2，长度 3。路径压缩执行后，parent[5]、parent[4]、parent[3] 全部变成 2，树从“一条小链”变成“一把小扇子”：2 直接挂着 3、4、5 三个孩子。

这个例子的要点是：压缩并不“额外”做什么，它只是把 find 已经走过的那几步，用赋值的方式“记下来”。下次再 find(5)、find(4)、find(3)，全部一步到位。如果整个序列里只有这一次 find，压缩前后的总开销几乎一样；但序列越长、重复查询越多，压缩的收益就越大。

7.8 走查给我们留下的三句话

把整个第 7 章浓缩成三句话：第一，合并只改根，不改成员；第二，find 的路径决定一切代价；第三，压缩和按秩合并，一个让旧路变短，一个让新树变矮。这三句话能回答绝大多数并查集面试题的“为什么”。

8 应用：从图论到刷题

8.1 无向图的连通分量

第一个应用最直接：统计无向图的连通分量个数。图的 n 个顶点先各自成组；然后遍历每条边 (u, v)，执行 union(u, v)。所有边处理完后，有多少个根，就有多少个连通分量。

为什么正确？连通分量是“通过边互相可达”的等价类：如果 u 和 v 之间有一条边，它们必然属于同一个分量，union 就把它们放进同一个集合；如果 u 和 v 之间有一条路径，路径上的边会依次把它们所在的集合合并，最终也落入同一个集合。处理完全部边之后，两个顶点同组的充要条件就是它们在图里连通。

这个过程的代码短得惊人：

const uf = new UnionFind(n);
for (const [u, v] of edges) uf.union(u, v);

const components = new Set<number>();
for (let i = 0; i < n; i++) components.add(uf.find(i));
console.log(components.size);

和深度优先遍历数连通分量相比，并查集版本的好处是动态：图可以一边加边一边查询“目前有几个分量”、“这两个点现在通不通”。DFS 每加一条边都要重新跑一遍，并查集则每次合并 O(α(n)) 搞定。这也是“动态连通性（dynamic connectivity）”问题的标准解法。

图中左边是一张无向图，右边是对应的并查集森林：A、B、C 连通，D、E 连通，所以有两个连通分量。注意并查集并不保存图的形状，它只保存“谁和谁同组”，图里的边信息在合并完成后就“用完即弃”了。

8.2 判断图中是否有环

并查集还能在 O(m α(n)) 的时间内判断一个无向图有没有环，思路非常巧妙：遍历每条边 (u, v)，如果 u 和 v 已经连通（find 结果相同），就说明这条边是“多余”的，它会让图出现环；否则把两个端点合并。

为什么？想象并查集森林是“已经确认连通”的关系。遍历到一条边时，如果它的两个端点早已通过其他路径连通，那么加上这条边，就形成了第二条路径，图中必然有环。反过来，如果每次都在端点不同组时才合并，那么被合并的边恰好构成一棵“生成森林”，产生环的那条边永远不会被合并。

图中的 C2 节点代表“第二条 C”，用加粗红边画出了典型的环边：处理边 B-C 时，B 和 C 已经通过 A 连通，所以这条边是多余的。判断“是否多余”只需要一次 connected 查询，而 connected 就是两次 find。

把判断环的代码写成函数，只需要十几行：

function hasCycle(n: number, edges: [number, number][]): boolean {
  const uf = new UnionFind(n);
  for (const [u, v] of edges) {
    if (uf.connected(u, v)) return true; // 已经连通，成环
    uf.union(u, v);
  }
  return false;
}

注意这个算法针对的是无向图。有向图的环判断是另一回事（通常用 DFS 染色或拓扑排序），不能直接套用并查集——因为并查集只关心“是否互相可达”，不关心边的方向。

8.3 Kruskal 最小生成树

第三个应用是并查集最著名的“主场”：Kruskal 最小生成树算法。图系列第 12 篇会详细讲图的最小生成树，这里先埋下伏笔。

Kruskal 的思路是贪心：把所有边按权重从小到大排序，然后依次尝试加入。每条边加入前，用并查集检查它的两个端点是否已经连通：如果没连通，说明加入它不会形成环，就加入生成树并 union 两个端点；如果已经连通，就跳过。当加入的边数达到 n-1 时，就得到了一棵最小生成树。

算法正确性的关键是“连通判断必须足够快”：边数 m 可能高达几十万，每条边都要做一次 connected 和可能的 union，总共 O(m α(n))，几乎就是 O(m)。如果没有并查集，每尝试一条边都要重新做一次连通性检查，复杂度立刻爆炸。可以在图论实验室里亲手试一下 Kruskal 的演示，拖动节点、改变边权，看看贪心选择的过程。

下面的代码是 Kruskal 的骨架，union 返回布尔值表示“这次合并是否真的发生了”：

function kruskal(n: number, edges: [number, number, number][]): number {
  edges.sort((a, b) => a[2] - b[2]); // 按权重排序
  const uf = new UnionFind(n);
  let cost = 0;
  let count = 0;
  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) { // 合并成功：没有成环
      cost += w;
      count++;
      if (count === n - 1) break; // 树已经连通
    }
  }
  return count === n - 1 ? cost : -1; // -1 表示图不连通
}

这里 union 需要返回布尔值，所以实现时给 union 加一个返回值：根相同返回 false，合并成功返回 true。这个小小的改动在 Kruskal、统计生成树边数等场景里非常常用。

8.4 岛屿数量

经典的 LeetCode 200“岛屿数量”也可以用并查集做。二维网格里，‘1’ 是陆地，‘0’ 是水，上下左右相邻的 ‘1’ 属于同一座岛。DFS/BFS 的解法很直观，但并查集版本同样自然：把每个陆地格子当成一个元素，扫描网格，遇到相邻的陆地就 union，最后数一数有几个根，再排除掉水格。

实现时先把二维下标压成一维：i × n + j。扫描顺序可以只检查“右邻居”和“下邻居”，因为扫描到每个格子时，它和左边、上边的合并已经发生过了。最后统计所有陆地的 find 结果去重。

网格 [[1,1,0],[1,1,0],[0,0,1]] 有两块不相连的陆地：左上角的四格组成一座岛，右下角单独一格是另一座岛。并查集最后给出两个根，答案就是 2。岛屿数量问题的本质就是“网格上的连通分量个数”，和 8.1 是同一个问题换了一身衣服。

完整的岛屿数量代码如下，注意一维下标、陆地标记和方向数组的配合：

function numIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const uf = new UnionFind(rows * cols);
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] !== "1") continue;
      for (const [di, dj] of dirs) {
        const ni = i + di;
        const nj = j + dj;
        if (ni < 0 || ni >= rows || nj < 0 || nj >= cols) continue;
        if (grid[ni][nj] === "1") uf.union(i * cols + j, ni * cols + nj);
      }
    }
  }

  const roots = new Set<number>();
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === "1") roots.add(uf.find(i * cols + j));
    }
  }
  return roots.size;
}

这里为了代码直观，四个方向都检查了；性能优化版可以只检查“右”和“下”两个方向，效果完全一样。陆地格子的数量就是参与并查集的元素数量，水格完全不参与。

8.5 朋友圈（LeetCode 547）

“朋友圈”问题给一个 n×n 的矩阵 M，M[i][j] = 1 表示 i 和 j 是直接朋友关系（矩阵对称，M[i][i] = 1）。朋友圈被定义为直接或间接朋友组成的集合，问有多少个朋友圈。翻译成并查集语言：对每个 M[i][j] === 1 的 i、j 执行 union(i, j)，最后统计根的数量。

注意矩阵对称且对角线为 1，扫描时可以只处理 j > i 的上三角，避免重复合并。这个问题的并查集写法和统计连通分量几乎一模一样，因为朋友圈本质上就是“朋友关系图”的连通分量——只不过关系由矩阵给出，而不是边列表。

function findCircleNum(m: number[][]): number {
  const n = m.length;
  const uf = new UnionFind(n);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (m[i][j] === 1) uf.union(i, j);
    }
  }
  const roots = new Set<number>();
  for (let i = 0; i < n; i++) roots.add(uf.find(i));
  return roots.size;
}

这道题还有一层“社交网络”的直觉：朋友圈就是“朋友关系”这个等价关系的等价类。并查集天生就是为等价类设计的——同组、同分量、同圈子，都是同一个抽象。

8.6 冗余连接（LeetCode 684）

“冗余连接”给一棵 n 个节点的树，外加一条边，构成一个有 n 条边的无向图，要求找到那条多余的边。并查集解法极其优雅：按顺序处理每条边，如果两个端点已经连通，那么这条边就是冗余的，直接返回它；否则合并。

这个思路和 8.2 判断环一模一样：处理到某条边时，它的两个端点已经通过之前的边连通，说明之前的边已经形成了一条通路，加上这条边就形成了环，而题目保证只有一条多余的边，所以它就是答案。整道题十几行代码，主要成本就是并查集的 find。

图中 1-2-4 和 1-3-4 构成了环，边 (3,4) 就是冗余连接：处理它时 3 和 4 已经连通。这里要注意题目的细节：如果有多条冗余边，答案要求返回“输入顺序中最后出现的那条”，所以处理边时按输入顺序进行，第一次发现“已连通”就返回，答案自然正确。

8.7 应用的共同点

回看这五个应用（连通分量、判环、Kruskal、岛屿、朋友圈、冗余连接），它们的模式惊人地一致：把元素丢进并查集，按某种顺序执行 union，在合并前用 connected 问一个问题。不同的只是“元素是什么”“什么时候 union”“问的问题是什么”。掌握了 find、union、connected 三个 API，这些题都是同一道题的换皮。这也解释了为什么并查集是面试和竞赛的常客：代码少、模式固定、覆盖面广。

如果把这些应用排成一行，你还会发现一个进阶规律：并查集适合回答“静态问题的动态版本”。图论里很多问题先问“最终状态”，比如“图里有多少分量”；加上并查集后，就能边改边问，比如“现在加了一条边，分量还剩几个”。这种“把离线问题变成在线问题”的能力，是并查集区别于 DFS/BFS 的最大价值。

8.8 并查集与 DFS/BFS 的对比

统计连通分量、判断两个点是否连通，DFS/BFS 也能做，为什么还要并查集？答案藏在“动态”两个字里。

DFS/BFS 的做法是：从某个未访问的顶点出发，把整个连通分量遍历一遍并打上标记，然后找下一个未访问顶点，直到所有顶点都被访问。它适合“图已经固定”的场景：跑一次 O(n + m)，得到全部分量。但它的输出是“一次性快照”——图一旦加边，快照就过期了，想更新答案只能重新跑一遍。

并查集的优势是增量：每加一条边，只需要 O(α(n)) 的代价更新结构，随时可以查询任意两个点的连通性。适合的场景包括：社交网络实时加好友、地图上动态修路、联机游戏的队伍实时合并。反过来，如果图从不变化、只需要一次完整的分量列表，DFS/BFS 往往更简单直接，因为它还能顺手输出“每个分量包含哪些顶点”，而并查集只回答“谁和谁同组”。

所以选型的口诀是：图静止，用 DFS/BFS；图在动，用并查集。两者不是竞争关系，而是互补关系——很多题目甚至两者都会出现，比如先 DFS 建图、再用并查集维护后续变化。

8.10 应用速查表

把本篇的应用收成一张速查表，做题时可以直接对号入座：

题目/场景	元素是什么	union 的时机	答案怎么算
连通分量	顶点	每条边	统计根的个数
判断无向图环	顶点	每条边	遇到已连通即成环
Kruskal	顶点	按权重取边	累加选中边的权重
岛屿数量	陆地格子	相邻陆地	统计陆地根的个数
朋友圈	用户	直接朋友关系	统计根的个数
冗余连接	顶点	按输入顺序取边	第一条已连通的边

表格读法的要点：“答案怎么算”几乎总是“统计根”或“判断已连通”二选一。把题目翻译成“元素 + union 时机 + 根的含义”三步，并查集题就解了一半。

8.9 更多现实场景

除了刷题，并查集在真实系统里也随处可见。编译器把“同名变量”和“类型别名”做等价替换时，可以用并查集维护类型之间的等价关系；数据库里做“分组合并”时，可以用它快速合并重叠的集合；游戏里的阵营系统，把“结盟”和“查询敌友”翻译成 union 和 connected，几乎是字面意义上的“朋友圈”问题。

还有一个经典场景是“区域填充”：像素网格上的连通区域（比如图片里的色块、地图上的国家）可以用并查集合并相邻的同色像素，一边扫描一边合并，最后统计根的数量。这和岛屿数量是同一个问题的不同包装。这些场景共同说明一件事：凡是“动态等价关系”，都值得想想并查集。

9 变体：带权并查集与可撤销并查集

9.1 带权并查集：不只是“同不同”，还要知道“差多少”

基本并查集只能回答“在不在同一个集合”。可很多问题需要更细的信息：食物链问题里，同类、吃、被吃三种关系；区间覆盖问题里，“x 比 y 大多少”；天平称量问题里，“x 和 y 的差是多少”。这些场景要用带权并查集（weighted union-find）。

带权并查集在每个节点上额外存一个“到父亲的权值”weight[x]，表示 x 与 parent[x] 之间的关系量（差值、偏移量，或模意义下的类别）。find 不再只是压缩路径，还要在压缩时累加权值，使 weight[x] 变成“x 到根的权值”；union 时则根据已知的两个差值反推根之间的差值，把两个集合挂起来。

图中每个节点带一个到父亲的权值：C 相对 A 偏移 +1，A 相对根偏移 +3，所以 C 相对根的偏移是 +4。find 时把这些偏移累加，就能回答“C 和根差多少”。带权并查集的关键难点是压缩时权值的传递公式，写错一个符号，整个答案都会错。

带权并查集的代码骨架如下（以“差值”为例）：

class WeightedUnionFind {
  parent: number[];
  weight: number[]; // weight[x] = x 相对 parent[x] 的差值

  constructor(n: number) {
    this.parent = new Array(n);
    this.weight = new Array(n).fill(0);
    for (let i = 0; i < n; i++) this.parent[i] = i;
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      const root = this.find(this.parent[x]);
      this.weight[x] += this.weight[this.parent[x]]; // 累加偏移
      this.parent[x] = root;
    }
    return this.parent[x];
  }
}

注意累加顺序：先把父亲“变成根”这件事递归做完，再把父亲的偏移加到自己的 weight 上，最后自己才指向根。顺序错了，weight 就错。union 的写法比基本版复杂一些，需要根据“已知 x 与 y 的差值”反推两个根之间的差值，这里不展开推导，记住“带权 = 在压缩时维护一条可累加的边权链”就够了。

一个值得记住的心法：带权并查集把“关系”也变成了可合并的信息。基本并查集合并的是“同组/不同组”这个布尔关系；带权版合并的是“差值、倍数、模类别”这类数值关系。只要关系满足“能沿路径传递、能在根之间反推”，就能塞进并查集。做题时看到“A 比 B 大 3、B 比 C 大 2，问 A 比 C 大几”，第一反应就该是带权并查集。

9.2 可撤销并查集：一句话预告

普通并查集只能合并，不能“撤销”最近一次合并。可撤销并查集通过记录每次合并修改了哪些 parent 和 rank，配合栈来支持回滚。它不能路径压缩（否则历史信息丢失），所以复杂度退化为 O(log n) 每次，常和“离线分治”配合，解决“只保留时间窗口内的边”这类动态问题。详细内容以后有机会单独开篇。

它的大致形状是：union 之前把“被挂的根、原来的 parent 值、rank 是否变化”压进栈；撤销时从栈顶弹出，把 parent 和 rank 恢复原样。由于每棵树的深度被按秩合并控制在 O(log n)，栈里记录的信息量也是 O(log n) 级别。理解它不需要新知识，只需要记住“把改动记下来，就能改回去”。

9.3 变体小结

带权并查集解决“关系有数值”的问题，可撤销并查集解决“历史要回溯”的问题，它们都在基本并查集的地基上加了一层状态。学并查集时，先把基本版的三件套写熟，再按需扩展：绝大多数题目用基本版就够了，变体是锦上添花。记住一个原则：变体不是新结构，而是基本版加了一层“额外的边信息”或“额外的历史栈”。

10 实现细节与常见坑

10.1 初始化与“根指向自己”

用 parent[i] = i 表示根，代码最简洁；但要注意循环边界，n 个元素编号 0 到 n-1，数组长度 n。如果题目编号从 1 开始（比如 684 题的节点编号 1 到 n），可以把数组开成 n+1，下标 0 空着不用，避免每次都要减一。这类“1 基 vs 0 基”的错误在并查集题目里非常常见，初始化时多看一眼就能避免。

10.2 递归 find 的栈风险

路径压缩的递归写法很美，但如果树很深且没有按秩合并，递归深度可能达到 n，导致栈溢出。两种解法：用迭代版 find；或者确保 union 一定带按秩合并。工程上建议默认写迭代版，面试时递归版 + 按秩合并也够用。如果递归版和按秩合并同时上，树的深度被控制在 O(log n) 以内，栈深度一般不是问题。

10.3 路径压缩后 rank 不更新

压缩会降低真实高度，但 rank 保留原值。这是正确的，不要试图在 find 里更新 rank。任何“rank 必须等于真实高度”的想法都会把代码改复杂，并且破坏复杂度保证。请把 rank 理解成“合并历史的记录”，而不是“当前真实高度”的实时测量。

10.4 union 返回值的用处

很多题目需要知道“这次合并是否真的发生了”（比如统计生成树边数、统计剩余连通分量个数）。可以把 union 改成返回布尔值：rx === ry 时返回 false，否则执行合并并返回 true。Kruskal 统计 n-1 条边时就会用到，8.3 节的代码就是这么写的。

10.5 并查集不能快速“分裂”

并查集支持合并，不支持删除、拆分：把一个集合拆回原来的两个集合，需要重建或使用可撤销变体。做题时看到“删除”需求，先想想能不能离线倒序处理——正着删等于反着加，这是经典套路。比如“不断删边，问连通分量”的题，往往先把所有操作读进来，倒过来变成“不断加边”，就回到了并查集的主场。

10.6 按大小合并的额外福利

如果按大小合并，size 数组初始全 1，合并时把 size 累加到新根。相比按深度合并，它还有一个额外好处：随时知道每个集合有多大。很多题（比如“合并后输出最大集合大小”）会用到这个信息，这时候按大小合并比按深度合并更顺手。两种合并方式的复杂度同级，选哪种取决于题目是否需要集合大小。

10.7 路径压缩与 rank 一起写时的顺序

标准实现里，find 和 union 的调用顺序也有讲究：union 内部必须先 find，拿到根后再比较 rank。有人会为了省事在 union 里直接比较 parent[x] 和 parent[y]，这在树还没有压缩时碰巧可能正确，但一旦树的结构变了就会出错。永远记住：比较根之前，先 find。

10.8 多组测试数据的初始化

刷题时一个隐蔽的坑是“多组测试数据共用同一个并查集对象”：上一组数据的合并结果会污染下一组。解决方法是每个测试用例新建一个 UnionFind 实例，或者在每组数据开始前重新初始化 parent 和 rank。看似是小事，但它制造的错误极难排查——结果随机对、随机错，很多人会怀疑算法本身。

10.9 二维坐标压一维

处理网格题时，把 (i, j) 压成一维下标 i × cols + j 是标准做法，但乘数必须是列数 cols，不是行数 rows。这个顺序写反，下标就会重叠或越界，合并关系随之错乱。推荐写一个小工具函数 idx(i, j)，所有访问统一走它，既防手滑，也让代码更清晰。

10.10 把“并查集类”写成一个模板

工程和刷题里，并查集代码几乎从不改动，值得写成固定模板：parent 数组、rank/size 数组、find（带路径压缩）、union（返回布尔值）。每次用到时直接抄模板，把精力留给“元素是什么、什么时候 union”这两个真正的问题。模板写熟之后，你会发现并查集题的平均用时比其他数据结构题短得多。

11 术语小词典

把本篇出现过的关键术语集中收进一个小词典，方便复习时快速查词。每个词条都给一句“人话版”解释，够用就好。

并查集（union-find，DSU）：一种维护若干不相交集合的数据结构，支持合并两个集合（union）和查询两个元素是否同组（find/connected）。中文名“并查集”三个字分别对应合并、查询、集合。

不相交集合（disjoint set）：彼此没有公共元素的集合族。并查集维护的多个集合两两不相交，任何一个元素恰好属于一个集合。

代表（representative）：每个集合选出的“发言人”，在并查集里就是树的根。判断两个元素是否同组，等价于判断它们找到的代表是否相同。

森林（forest）：若干棵互不相交的树组成的集合。并查集在任意时刻的状态都是一片森林，每棵树对应一个集合。

双亲表示法（parent representation）：只用“每个节点的父亲”来存储树的方式，对应一个 parent 数组。第 4 篇介绍过它，并查集是它最著名的应用。

find：给定元素，沿着 parent 指针向上走到根并返回根的操作。它是并查集的底层引擎，union 和 connected 都建立在它之上。

union：给定两个元素，把它们所在的集合合并成一个的操作。实现上是“两次 find + 把一根 parent 指向另一根”。

connected：查询两个元素是否同组的操作，通常实现为“两次 find 的结果是否相等”。

根（root）：没有父亲的节点。在并查集里，根是集合的代表；按“根指向自己”的约定，parent[root] === root。

路径压缩（path compression）：find 向上走时，把沿途节点的 parent 直接改成根，让后续查询一步到位。它是并查集的两个核心优化之一。

折半压缩（path halving）：路径压缩的轻量变体，find 每走一步就把当前节点挂到爷爷节点下面，代码更短，压缩效果略弱但够用。

按秩合并（union by rank）：union 时把矮树挂到高树下面，只有两棵树一样高时新树高度才加一。它让树的高度保持在对数级别。

按大小合并（union by size）：按秩合并的一种，用“节点数”代替“高度”决定挂的方向，还能顺便维护每个集合的大小。

秩（rank）：按深度合并时，每个根记录的高度估计值。路径压缩后它不再等于真实高度，但仍是合法的上界。

均摊复杂度（amortized complexity）：把一系列操作的总代价平均到每个操作上的复杂度。并查集的 O(α(n)) 是均摊意义下的。

反阿克曼函数（inverse Ackermann function）：阿克曼函数的反函数，增长慢到几乎可以看作常数。路径压缩 + 按秩合并后，单次操作的均摊复杂度就是 O(α(n))。

动态连通性（dynamic connectivity）：图一边变化一边回答连通性查询的问题。并查集是这类问题最常用的工具。

连通分量（connected component）：无向图里“互相可达”的最大顶点集合。并查集处理完全部边后，每个根对应一个连通分量。

生成树（spanning tree）：连通图里包含全部顶点、边数最少（n-1 条）且保持连通的子图。Kruskal 用它构造最小生成树。

Kruskal 算法：按权重从小到大尝试加边、用并查集判环的最小生成树算法，总复杂度主要由排序决定。

带权并查集（weighted union-find）：在 parent 之外再存一个“到父亲的权值”，find 时累加、union 时反推，能回答“两个元素差多少”的问题。

可撤销并查集（rollback union-find）：用栈记录每次合并修改的位置，支持回滚最近一次合并的变体；代价是不能路径压缩，单次操作 O(log n)。

离线倒序（offline reversal）：把“删除”操作倒过来变成“插入”，再用只支持插入的并查集解决问题，是处理动态删除问题的经典套路。

等价类（equivalence class）：满足自反、对称、传递关系的元素分组。同组、同分量、同圈子都是等价类，并查集天然适合维护它们。

这份词典不需要背，读到不认识的词回来翻一翻即可。术语熟悉之后，第 19 篇讲线段树和树状数组时，你会发现自己已经能读懂大半“树的话”。

12 操作复杂度速查表

把各种实现方式放在一起对比，一眼看清“优化到底优化了什么”：

实现	find 最坏	单次均摊	额外空间
朴素（无优化）	O(n)	O(n)	O(n)
只按秩合并	O(log n)	O(log n)	O(n)
只路径压缩	O((m+n) log n) / m 均摊	接近 O(log n)	O(n)
路径压缩 + 按秩合并	O(α(n)) 均摊	O(α(n))	O(n)

补充说明：并查集的空间永远是 O(n)——parent 数组加上可选的 rank 或 size 数组，都是 n 个整数，与操作次数无关。这里的 n 是元素个数，m 是操作次数。表里“只路径压缩”的均摊写法在工程上足够准确，竞赛里的精确界是 O((m+n) log n) 总量，但这不影响“它接近线性”的直觉。

这张表还有一个用途：面试被问“为什么并查集快”时，不用背公式，直接说“两个优化分别管住树的深度和路径长度，合起来让每次操作平均只需常数步”，就能把核心讲清楚。至于 α(n) 的具体值，面试官通常只期待你认识这个符号，不会要求推导。

本篇要点小结

第一，并查集 = 森林 + 双亲表示法。每个集合一棵树，根是代表；parent 数组只存“向上”的信息，不需要孩子指针。

第二，find 是灵魂，union 是皮囊。一切操作最终都落到 find：connected 是两次 find 比较，union 是两次 find 加一根指针。

第三，两个优化一起用。路径压缩在 find 时修路，按秩合并让 union 挂得更聪明；合起来均摊 O(α(n))，几乎等于常数。

第四，应用模式固定。连通分量、判环、Kruskal、岛屿、朋友圈、冗余连接，全是“按顺序 union + 关键时刻 connected”。

13 自测题（附答案）

14 下一篇预告

下一篇是《树系列第 19 篇：线段树与树状数组》。树系列前 18 篇讲的树，节点要么是“存数据”的普通节点，要么是“代表集合”的并查集节点；而线段树和树状数组是另一类神奇的树——它们的叶子存原始数据，内部节点存区间统计信息，用树的结构把“区间查询 + 单点更新”从 O(n) 压到 O(log n)。你会看到数组怎么“伪装”成树、区间求和与最值怎么拆分成 O(log n) 个子区间，以及树状数组为什么是线段树的“轻量小弟”。敬请期待。

15 写在最后

并查集是树系列里最“不像树”的一篇：它没有孩子指针、没有显式的遍历、没有递归建树，只有一行 parent 数组和两个操作。但正是这种极简，让它成为“树的思想”最锋利的一次输出：把集合当成树，把根当成代表，把连通性变成一次向上走。从朋友圈到 Kruskal，从判环到冗余连接，同一个思想反复出现。

如果你今天只有十分钟动手时间，我建议做三件事：第一，手写一个带路径压缩和按秩合并的 UnionFind 类，跑一遍第 7 章的 7 个操作，对照表格检查 parent 数组；第二，用并查集写一遍“岛屿数量”或“冗余连接”，感受“模式固定”的力量；第三，打开图论实验室，亲手点一遍 Kruskal 的演示。做完这三件事，并查集就会从“看过”变成“会写”。

下一篇，《树系列第 19 篇：线段树与树状数组》，我们继续用树解决区间问题。第 19 篇见。