并查集详解：动态连通性与路径压缩优化实战-开发者社区

并查集这名字，我第一次看到的时候真觉得挺唬人，总感觉是什么高深莫测的高级数据结构。结果认真学完之后才发现，它大概是所有“听起来高大上”的数据结构里最朴素的一个：一个数组，几个循环，却能解决一类非常经典的连通性判断问题。我当年是在做图论题目时被它救了一命，当时题目让判断两个节点在动态变化的图里是否连通，查询次数特别多，我第一反应是每查一次就跑一遍 BFS，结果数据一加大直接超时，超到怀疑人生。后来经人提醒才认真补了并查集这块，从此“动态连通性”类的题目再也没坑过我。

并查集的英文名 Union-Find 其实比中文名好懂得多：Union 是合并，Find 是查找。它干的事就两件：把两个元素所在的集合合并成一个集合，以及查找某个元素属于哪个集合。有了这两个操作，就能随时查询任意两个元素是否在同一个集合里了。这个数据结构适合谁来学？只要你学过数组和递归，能在代码里写循环，就可以学。它不需要复杂的平衡旋转，不需要高深的数学推导，非常适合作为你掌握的第一个“正经算法”级别的数据结构。

1. 先说清楚：并查集到底解决了什么问题

我后来发现，很多初学者卡在并查集上，不是卡在代码，而是卡在“不知道这玩意到底在干嘛”。所以先别急着写代码，我们先用大白话把它的核心逻辑捋清楚。

最关键的一点：并查集是一个维护“动态连通性”的数据结构。“动态”是什么意思？意思是图的连接关系是逐渐加入的，你随时可能加一条边进去，然后又随时可能问“这两个点在当前这张图里能不能连上”。如果你用 BFS 或 DFS 来做，每加一条边，整个图的连通状态就要重新算一遍，查询一多，代价非常高。而并查集可以在几乎常数时间内完成一次合并或查询，这就是它最大的价值。

理解它的最简单方式，是把它想象成一群人在“认老大”。每个集合都会选出一个“代表元素”，也就是老大。集合里的每个成员，要么自己就是老大，要么直接或间接地指向那个老大。判断两个人是不是一个团队的，就只看他们的老大是不是同一个人。要把两个团队合并起来，就是让其中一个团队的老大改认另一个团队的老大当老大。

这套听起来像江湖黑话的理解，对应到代码里其实就是并查集的全部核心。别看它简单，后面所有优化和变种，都是在这个“认老大”模型上长出来的。

1.1 一个非常朴素但能讲清本质的小例子

举个例子你就明白了。假设有六个人，编号 1 到 6，初始时每个人都自成一派，各自是自己的老大。

现在合并 1 和 2，表示这两个人是同一团队。
再合并 3 和 4。
再合并 2 和 4。

经过这三步之后，1、2、3、4 应该属于同一个团队，而 5、6 各自独立。并查集要保证的是：不管合并操作的顺序有多乱，我们随时可以查询 “1 和 4 是不是同一团队”，并且在每次合并和查询的时候都很快。

如果用朴素数组去模拟这件事，每个人存一个“老大编号”，合并的时候需要把一个团队里所有人全部改一遍。最坏情况下要遍历整个数组，做 m 次操作就是 O(n·m)，数据一大就完全跑不动。并查集的高明之处在于用树形结构去组织关系：合并时只改一个根节点，查找时顺着 parent 指针往上走，最后能把均摊复杂度压到接近常数。

这个例子背后有一个很微妙的点，我想单独拿出来说：并查集只关心“哪些元素属于同一个集合”，完全不关心集合内部的顺序和结构。它不维护集合里元素的前后关系，不维护树的左右子树，更不关心两个元素是怎么连起来的。只要最终能回答“在不在同一个集合”，其他一切都是多余的。记住这个定位，后面看各种变种题时就不容易迷糊。

1.2 基本操作：初始化、查找、合并

并查集最核心的操作就三个，其他所有东西都是在这三个操作上做文章。

初始化：让每个元素单独成为一个集合，即parent[i] = i。因为一开始谁和谁都没关系，每个人都是自己的老大，也是自己所在树的根。

查找：找到某个元素所在集合的根。从任意一个元素出发，沿着parent一路往上跳，跳到某个满足parent[x] == x的点，那个点就是根。

合并：把两个元素所在的集合合并成一个。先分别find出两个元素的根，如果根相同，说明它们在同一个集合里，不需要任何操作；如果根不同，就把其中一个根接到另一个根下面，比如parent[rootX] = rootY。

到这里，并查集的概念部分其实已经讲完了。但如果你直接按这个思路去写代码，就会遇到我当年遇到的问题：在极端输入下还是挂。因为朴素版的合并方式可能导致树退化成一条很长很长的链，查找一次要跳完整条链，复杂度退回 O(n)。所以接下来必须聊两个关键优化：路径压缩和按秩合并。

2. 代码实现：从朴素版到标准优化版

我个人的建议是，学并查集不要一上来就背最终优化版模板。先把最朴素的版本写通，跑通几个小用例，再一步一步把优化加上去。这样你在 Debug 的时候能清楚地知道每个变量在干什么，而不是拿了一个看似高深的模板，一遇问题就彻底懵圈。

2.1 朴素版：先把流程跑通

用 C++ 写一个最朴素的版本，大概是这个样子：

const int MAXN = 100005; int parent[MAXN]; // 初始化：每个节点指向自己，即自成一派 void init(int n) { for (int i = 0; i <= n; i++) { // 习惯多初始化一位，避免越界 parent[i] = i; } } // 查找：递归往上跳，直到根 int find(int x) { if (parent[x] == x) { return x; } return find(parent[x]); // 递归找根 } // 合并：把一个根挂到另一个根下面 void unionSets(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { parent[rootX] = rootY; } }

有几个小细节，新手很容易踩坑，我在这里提前说清楚：

第一，union是 C++ 的标准库函数名，也是一些语言的关键字，所以我习惯把函数名写成unionSets或merge，避免编译报错和名字冲突。

第二，parent数组初始化时，下标到底从 0 开始还是从 1 开始，取决于题目里的节点编号。如果节点编号是 1 到 n，那你至少要初始化到 n；如果是从 0 开始，也要把 0 初始化到。很多题目的坑不在算法本身，而在初始化漏了一位，导致某些节点始终没有正确的 parent，查出来的根是错的。

第三，递归版find在链比较深的时候会爆栈。这也是为什么很多长年写竞赛代码的人会刻意写成迭代版。初学者可以先不用关心爆栈问题，先拿递归版理解逻辑就够了。

2.2 路径压缩：让查找“顺路修路”

朴素版的问题具体出在哪？来看一个典型的坏场景。

依次执行unionSets(1, 2)、unionSets(1, 3)、unionSets(1, 4)，如果在这个实现里每次都把左节点所在树的根接到右节点所在树的根上，那么树的结构会变成一条链：

1 -> 2 -> 3 -> 4

也就是说parent[1] = 2，parent[2] = 3，parent[3] = 4，parent[4] = 4。如果此时要find(1)，就得沿着链往上跳 3 步。如果数据规模是十万、百万，链就会长到十万、百万，而每次合并都要做两次find，整体复杂度瞬间爆炸，直接退化到 O(n²) 级别。

路径压缩的做法简单到令人发指：在查找过程中，顺手把沿途经过的所有节点，全部直接挂到根节点下面。

int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 递归返回时，沿途每个点都指向根 } return parent[x]; }

就这么几行代码，效果极其惊人。假设刚才那条链执行了find(1)，执行完之后，parent[1] 直接变成 4，parent[2] 也变成 4，parent[3] 也变成 4。整条链被压扁成了一层。以后再找任何节点的根，都只需要一步。

这个优化的名字叫“路径压缩”，表达的正是“查找时把路径上的节点压缩到根旁边”。用术语说，路径压缩配合另一种优化后，可以让单次操作的摊还时间复杂度降到反阿克曼函数量级，而这个函数增长慢到你可以直接把它当作常数。我当年第一次写出这个版本后，跑前面超时的题目，速度差距大到自己都不敢信。

我自己刷题这么多年的体会是：路径压缩这几行，是整个并查集从“能跑”到“好用”的分水岭。少了它，小数据随便跑，大数据必超时；有了它，绝大多数并查集题目都不用再担心时间。

2.3 按秩合并：把树的高度控制住

路径压缩解决的是“查询时把树压扁”，但它并不负责改变合并时的树形状。换句话说，如果合并的方式很不好，仍然可能先长出一棵很深的树，虽然路径压缩会在下次查找时把它压扁，但那次查找本身可能已经很慢了。按秩合并就是为了让树在合并过程中尽量保持矮胖。

什么是“秩”？最简单直观的秩就是树的高度。我们额外维护一个rank数组，rank[root]表示以 root 为根的这棵树的大致高度。合并两棵树时，把矮的树接到高的树上。当两棵树高度相等时，新根的高度才会加 1。这个策略能保证整体树的高度始终维持在 log 级别。

int rank[MAXN]; void init(int n) { for (int i = 0; i <= n; i++) { parent[i] = i; rank[i] = 0; } } void unionSets(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return; // 按秩合并：矮树接高树 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; // 高度相等，新树高度 +1 } }

注意，路径压缩会改变树的实际高度，所以这里的rank并不是精确的树高，而只是一个“上界”。不过这完全不影响我们用它来决定合并方向，因为哪怕它只是一个近似值，也已经足够让树保持矮胖了。

按我个人的实战体验，只加路径压缩已经能解决绝大多数题目。按秩合并更多是“锦上添花”，但它的价值体现在稳定性上：极端情况下，路径压缩前那次find本身就可能因树太深而很慢，有按秩合并兜底，整个过程都会更稳。我在递归版find里会尤其在意这点，因为树越深，爆栈风险越高。

2.4 迭代版 find 与细节取舍

如果你不喜欢递归，或者担心爆栈，可以用两遍循环实现迭代版路径压缩：

int find(int x) { int root = x; // 第一遍循环：找到根 while (parent[root] != root) { root = parent[root]; } // 第二遍循环：把路径上所有节点直接挂到根下面 while (x != root) { int next = parent[x]; parent[x] = root; x = next; } return root; }

第一遍先沿着链走到根，第二遍再从 x 开始走一遍，把沿途每个节点的 parent 都改成根。这种写法在数据结构上更“底层”，也完全不依赖系统递归栈。两种写法效果等价，选一种你顺手的就好。

关于要不要把按秩合并和路径压缩都写上，我的看法是：模板阶段都写上，因为这是标准做法；实际做题时如果为了省事，只写路径压缩也基本可行。真正要注意的是别把这两个优化混在一起时搞出逻辑错误，比如在递归版路径压缩里错误地维护了 rank 导致索引越界。

3. 实战：并查集在题目里的几种典型用法

概念搞清楚，代码也能写了，下一个问题就是：题目到底怎么出？我怎么知道这题该用并查集？

我的经验是这么总结的：只要题目里出现“动态判断两个点是否连通”“求连通块数量”“把若干个集合合并并统计关系”这些词眼，就可以往并查集上想。下面详细拆几种最常见的使用场景。

3.1 连通块计数问题

最经典的一个场景：给定 n 个节点和 m 条边，求整张无向图被分成了几个连通块。所谓连通块，就是图中的一批点，它们通过边能互相到达，它们就算同一个块。

用并查集的做法非常直白：初始化所有节点，然后每读进一条边(u, v)，就调用一次unionSets(u, v)。所有边处理完之后，统计有多少个parent[i] == i，这个数量就是连通块的个数。

这个解法为什么好？因为它完全不需要建图。普通图遍历题往往要先存边、建邻接表，再 BFS 或 DFS 扫一遍。并查集则是边读边处理，读完全部数据，答案也就出来了，时间复杂度接近 O(m)。

这里再补充一个很实用的小技巧：连通块数量可以在合并过程中动态维护。初始化时设answer = n，每次成功合并一次（也就是rootX != rootY时），就让answer--。这样最后直接用这个变量就行，不需要再遍历一遍parent数组去数根节点。这个技巧在多次查询的题目里特别好用。

3.2 动态连通性查询问题

第二类题型是“给定一对节点，问它们当前是否连通”。如果整张图的边不是一次性给完，而是操作过程中不断添加，那并查集几乎是唯一自然的选择。

举个例子：某社交网络有 n 个用户，系统不断给用户之间添加“好友关系”，同时随时查询两个人之间是否存在一条由好友链路组成的通路。用并查集写就是：

cin >> x >> y; if (find(x) == find(y)) { cout << "connected" << endl; } else { cout << "not connected" << endl; }

在这里，并查集的优势最明显：单次查询只需要几乎 O(1) 的时间。而如果用 BFS，每次查询都要从指定节点开始重新遍历整张图，谁会闲着没事在几百万节点的图里给你反复跑 BFS？

做这类题时，有一个我在实际中踩过的坑必须提醒你：如果题目里的查询和合并操作是交错出现的，比如“增加一条边 -> 查询一次 -> 再增加一条边 -> 再查询”，那所有操作必须严格按照输入顺序依次执行，绝对不能先把所有边合并完再处理查询。有些人读题不仔细，看到“图”字就默认建图，结果顺序一错，整份代码的结果全对不上。我建议在写代码前先在纸上按输入顺序模拟一个小样例，确认自己理解的是对的再动手。

3.3 图论算法中的并查集：Kruskal 最小生成树

要说并查集最经典的落地场景，那一定是 Kruskal 求最小生成树的算法。当年我觉得这个算法很神奇，后来想明白了，它就是并查集一个非常自然的应用。

Kruskal 的思路是：把图中所有边按边权从小到大排序，然后依次尝试加入每一条边。如果一条边连接的两个端点已经在同一个连通块里，那加上它就会成环，跳过；否则就把两个端点所在的集合合并，并把这边的边权加到答案里。循环直到加入 n-1 条边，最小生成树就建成了。

把这段描述翻成代码，你会发现真正属于 Kruskal 的核心逻辑就这么几块：排序、循环、并查集。

struct Edge { int u, v, w; bool operator<(const Edge &other) const { return w < other.w; } }; vector<Edge> edges; // 这里省略读入边的过程 sort(edges.begin(), edges.end()); int ans = 0; int cnt = 0; for (auto &e : edges) { int ru = find(e.u); int rv = find(e.v); if (ru != rv) { parent[ru] = rv; ans += e.w; cnt++; if (cnt == n - 1) break; // 已经构成生成树 } }

你会看到，“判断是否成环”靠的是并查集的 find，“合并连通块”靠的还是并查集的 union。整个算法里最频繁的操作就是 find 和 union，所以并查集的性能直接决定了 Kruskal 的成败。如果 find 退化成 O(n)，在 m 条边上就是 O(n·m)，那这个算法就废了。这也是为什么在最小生成树这种对性能敏感的题目里，路径压缩 + 按秩合并是标准配置，绝不偷懒。

4. 进阶：带权并查集，从一个偏门但重要的扩展说起

如果只学到上一章，并查集已经能覆盖挺大一片题目了。但真正让我觉得“并查集水很深”的，是带权并查集。初次接触时，我们只关心元素“在不在同一个集合”。但有些题目还会要求：在同一个集合里，元素之间还有什么相对关系。

比如告诉你 A 比 B 大多少，B 比 C 小多少，问 A 和 C 相差多少；或者食物链里谁吃谁；或者一排队伍里两个人之间隔了多少位置。这类题目如果不会带权并查集，写起来很绕，一个不小心就把自己绕晕。而一旦会了，很多题就是模板题。

4.1 带权并查集要解决什么问题

带权并查集的核心是在parent[x]的基础上，额外维护一个数组weight[x]，表示“x 到 parent[x] 的权值”。这个权值到底代表什么，完全由题目定义：可以是数值差，可以是倍数关系，也可以是方向关系。

举个例子，假设题目告诉你“元素值”上 x 比 y 大 3，那么我们就需要一种方式，把这种“x 相对 y 大 3”的关系存到并查集的结构里。当后续又告诉我们“y 比 z 大 2”时，我们就可以推理出 x 比 z 大 5。这套推理能不能落实成高效代码，就看带权并查集写得好不好。

如果不用带权并查集，也可以开一个邻接表来存差值关系，但合并两个大集合时效率就很低。带权并查集把关系压缩到了“每个节点到根的距离”上，合并和查询依然接近常数时间，这是它存在的意义。

4.2 权值累积与 find 路径压缩

最核心的难点在于：当find做路径压缩时，每个节点不能只是“改一下 parent 指向根”，还要把weight[x]同步更新成“x 到根节点的权值”。因为如果 x 的 parent 变成了根，那么 weight[x] 就必须从“x 到原父节点的权值”更新成“x 到根节点的权值”。

看一个具体实现，假设weight[x]表示“x 到 parent[x] 的数值差”，也就是：

value(x) - value(parent[x]) = weight[x]

那么递归版带权 find 可以写成：

int find(int x) { if (parent[x] == x) { return x; } int p = parent[x]; // 关键：先存下旧父亲 int root = find(p); // 递归找根，此时 p 已经指向根 weight[x] += weight[p]; // x 到根的权值 = x 到 p 的权值 + p 到根的权值 return parent[x] = root; // 路径压缩 }

这里有一个新手非常容易踩的坑：没有先保存旧的 parent[x]。如果不保存，在递归返回后，parent[x]已经变成了根节点，你再去取weight[parent[x]]，取到的就是“根节点到根节点的权值”，而不是“旧父亲到根的权值”。我第一次写的时候没注意，直接weight[x] += weight[parent[x]]，结果递归返回后 parent[x] 已经变了，权值加了两遍，怎么 Debug 都不过。所以这个保存旧父节点的动作，是带权并查集里决定生死的一步。

4.3 合并时的权值推导

find搞定之后，union也有新东西要处理。普通并查集合并时只需要把根接过去，带权并查集还要把权值关系也接过去，这需要推导一个公式。

假设我们已知x到rootX的关系是weight[x]，y到rootY的关系是weight[y]。现在题目告诉我们x比y大d，要我们把 rootX 接到 rootY 上，并算出weight[rootX]。

把符号理一理：

value(x) - value(parent[x]) = weight[x] value(x) = weight[x] + value(rootX) value(y) = weight[y] + value(rootY)

题目条件是value(x) - value(y) = d，代入之后：

(weight[x] + value(rootX)) - (weight[y] + value(rootY)) = d => value(rootX) - value(rootY) = d - weight[x] + weight[y]

所以当 rootX 接到 rootY 下面时，新的weight[rootX]就是d - weight[x] + weight[y]。

这个公式不需要死记硬背，因为不同题目里“d”的方向、weight 的定义都可能不同。我强烈建议在纸上画一个“x -> rootX、y -> rootY”的箭头图，标上已知的 weight，然后自己推一遍。如果你把公式记死，换个题目方向一变，就很容易出正负号错误，而这种错误往往小样例能过、大数据挂掉，排查起来非常痛苦。

带权并查集刚上手时确实有点绕，但多做两三道例题之后，你会慢慢形成“像做代数题”一样的直觉：看到关系条件就先写 value 等式，然后解出 root 之间的差值。这套思路一旦通了，食物链、相对距离、矛盾判断这类题基本就是同一个模板反复用。

5. 刷题与避坑：从入门到精通的实用路线

技术文章如果只讲概念和代码模板，价值其实是有限的。真正让你熟练的，永远是刷题和踩坑。所以这一整章我来讲讲我实际经历过的东西：应该按什么顺序刷题，会遇到哪些坑，怎么高效 Debug。

5.1 推荐刷题节奏

我自己的经验是，并查集的学习路径可以分成几个阶段，每个阶段目标不一样，不要跳着来。

第一阶段是验证模板。找一道只需要并查集基础操作的题，比如“朋友关系”“团伙判定”这类。这种题不需要任何高级技巧，你只要把模板敲熟，把 find 和 union 正确调用，就能 AC。这一阶段的核心目标是熟悉接口，以及锻炼“看到关系就想到合并”的反射弧。

第二阶段是结合图论。做连通块计数类、动态连通性判断类题目。你会发现并查集在处理这类题时“不太需要建图”，这对习惯 BFS 和 DFS 的人来说是一个观念冲击：原来不是所有图题都要遍历。做两三道之后，你会形成肌肉记忆：只要看到“判断连通”“图的动态变化”，就自动联想到并查集。

第三阶段是 Kruskal 最小生成树。当你有了图论基础之后，专门去刷 Kruskal 相关的题目。这个阶段能让你体会到并查集在“判定成环”和“合并集合”这两个能力上的完美组合，也会顺便复习一下贪心思想和排序。把这道坎过了，并查集在图论里的角色你就彻底内化了。

第四阶段是带权并查集。在基础操作完全熟练、几乎不再写错的前提下，再挑战带权并查集。这类题的重点不在模板，而在推导权值等价公式。我建议先做一两道例题，然后把公式推导过程完整地写在代码注释里，再去做其他带权题。这个阶段的收获会非常大，因为很多人的并查集之旅就止步于标准版，而带权扩展能让你的深度一下子拉开差距。

5.2 常见坑与调试技巧

接下来这部分，是我最想写给新人的。以下每一个坑，我都见过实体代码踩过：

第一个坑是路径压缩与递归返回顺序。有些人在写路径压缩时，会把递归和赋值写成错误的组合，导致返回的并不是根节点。最简单的排查方式是构造一条 3 到 4 个节点的链，反复调用 find，然后打印parent数组，看是不是每个节点都指向了根。这一步打印出来，所有问题都会现出原形。

第二个坑是合并前没有判断rootX == rootY。如果不判断，两个已经在一个集合里的点再合并一次，在统计合并次数、连通块数量、或者边数时就会多算。大部分题目结果表现不出来，但一旦题目要求输出“成功合并次数”，这里就必然出错。所以标准模板里一定要在 union 里先判根是否相等。

第三个坑是初始化范围。并查集的parent数组我见得最多的错误之一是只初始化到 n-1，结果某次访问了没有初始化的节点，查出来一个乱七八糟的根。统一做法是for (int i = 0; i <= n; i++) parent[i] = i;，多初始化一个位置也费不了多少事，但能帮你挡掉一类很隐蔽的越界错误。若是多组测试数据，还要记得每组数据重新 init，否则上一次的合并结果会污染下一次。

第四个坑是带权并查集的正负号。这个我在前面也提到过，带权并查集一旦正负搞错，小样例经常能过，大样例挂得莫名其妙。因为系统可能在各种方向关系的组合下，把方向性错误掩盖得很深。我每做一个带权题，都会手动模拟一组 3 到 4 个元素的数据，把合并后每个节点的 weight 都算一遍，再对照题目要求看方向是否正确。别嫌麻烦，这个习惯帮我省下了无数 Debug 时间。

还要分享一个我一直很受用的调试技巧：写并查集时，在合并后打印每个节点的 parent 数组和 weight 数组是个特别直观的调试图。你闭上眼脑补十遍树的结构是怎么变的，都不如实际打印一遍看得清楚。这个小动作几乎适用于所有数据结构调试，尤其对并查集这种“重结构、轻数据”的数据结构来说，效果奇佳。