并查集从原理到实战：高效判断图中两点是否连通

今天打卡第59天，栈、队列、二叉树、回溯、贪心、动态规划一路走下来，终于轮到图论里一个名声不大但出场率极高的数据结构——并查集。第一次听到“并查集”这个名字，很容易觉得是个偏门玩意，实际上它要回答的问题特别朴素：给定一张无向图，反复询问两个节点之间是否存在一条路径。代码随想录里这道“寻找存在的路径”，就是把这个问题原封不动搬到了 OJ 上：给定 n 个节点和 m 条边，再给一个起点和一个终点，能到达输出 1，不能到达输出 0。

如果你之前只接触过 DFS 和 BFS，可能会想“这不就是一次深度优先搜索的事吗”。但并查集的存在价值恰恰在于：它把“每次询问都搜索一遍”的成本，降成了“建图时合并一次、查询时几乎 O(1) 判断一次”。这种思路在社交网络关系、电路连通性、聚类算法底层实现里都能看到影子。这篇文章我会从理论原理讲到完整题解，再补上路径压缩和按秩合并的细节，以及我实际写代码时踩过的几个坑。不管你是训练营打卡成员，还是刚开始接触并查集的初学者，希望对你有帮助。

1. 为什么都到第59天了，还要专门拿一天啃并查集

1.1 反复询问“两点连不连”才是更常见的场景

很多讲图的教材，重点都放在最短路径、最小生成树上，DFS/BFS 给人的印象是“我总能找到路径”。可一旦把问题改成“给你 10 万个节点、20 万条边，再给你 10 万次询问，每次问 u 和 v 通不通”，用 DFS 的代价就很可怕了：最坏情况下，每一次询问都要把整张图遍历一遍，10 万次询问就是 10 万次 O(V+E)，再快的机器也顶不住。

这时候并查集就派上用场了。它的核心思路特别像现实里的“认亲”：

• 一开始每个人都只认识自己，每个人都是一个独立的家族；
• 给定一条边 (u, v)，就相当于说 u 和 v 是亲戚，把两个家族合并；
• 后面再问 u 和 v 是不是亲戚，只需要看一下他俩的“家族族长”是不是同一个人。

“寻找存在的路径”这道题把这一过程简化到了最直白的程度：先给出所有边，一次性建好连通关系，最后只问一次 s 能不能到 t。这其实就是并查集最基础的“建图 + 查询”场景。

1.2 DFS/BFS 和并查集的取舍边界

如果把 DFS/BFS 和并查集放在一起对比，各自的优势区间其实很清晰：

所以并不是说并查集取代了 DFS/BFS，而是它专门解决“连通性判断”这一个子问题。在“寻找存在的路径”这道题里，我们不关心路径长什么样，只关心 s 和 t 最终在不在同一个集合里，这正是并查集的甜区。打卡到了第 59 天再集中把并查集讲清楚，你会发现后面对抗“冗余连接”“省份数量”这类题时，核心代码基本不用改。

1.3 “并、查、集”三个字本来就是全部

我第一次学并查集的时候，试图从字面拆解它的设计思路。“并”指的是合并 union，把两个集合合成一个；“查”指的是查找 find，找到某个节点所属集合的根；“集”指的是集合，底层用一棵树表示一个集合。数据结构界很少有这么“名字即注释”的设计。

麻烦的地方只在于：它用数组模拟森林，而不是用指针。这会让第一次接触的人有点绕——明明是一棵树，为什么不直接用 struct Node？因为并查集的操作只需要知道“我的父节点是谁”，不需要左右孩子、不需要节点值，只需要一个 int 下标。用 vector father 就够了，不仅省空间，而且快。

2. 三个函数撑起整个数据结构：初始化、找根、合并

2.1 用一维数组表示多棵互不相干的树

并查集的底层模型是森林，每一棵树代表一个集合，树的根节点代表这个集合的“族长”。初始化时，我们认为图里还没有任何边，每个节点自成一棵树，所以每个节点的父节点都是自己：

vector<int> father; void init(int n) { father.resize(n + 1); for (int i = 1; i <= n; i++) { father[i] = i; // 自己是自己的根 } }

这里用 n+1 而不是 n，是因为节点编号从 1 开始，避免浪费一个下标也避免越界。如果你习惯从 0 编号，那用 n 也完全没问题。我后面写题解时统一按从 1 编号，因为代码随想录原题就是这么设定的。

2.2 find：沿着父节点指针一路向上，直到找到根

find 的作用是给定一个节点 u，返回它的根节点。实现方式就是不断往上走：

int find(int u) { while (father[u] != u) { u = father[u]; } return u; }

举个例子，如果合并后形成了这样的链：1 -> 3 -> 5，也就是 father[1] = 3, father[3] = 5, father[5] = 5。这时 find(1) 就会从 1 走到 3，再从 3 走到 5，发现 father[5] == 5，于是返回 5。注意这个返回条件：某个节点是根，当且仅当它的父节点指向自己。

这个 while 版本的 find 虽然能正确工作，但性能并不理想。如果合并时总是把一个长链的根接到另一个集合上，树会越来越深，find 最坏可能要走 O(n) 步。这也是后面第 4 节要讲路径压缩的原因。

2.3 join：合并两个集合，先找到各自的根再说

合并操作最直观的写法是“直接让一个根认另一个根做父节点”。但千万不要合并叶子节点——如果只把 u 的父节点改成 v，那么 u 原来的兄弟们并不会跟着走，集合就分裂了。正确做法是先找到两个集合的根：

void join(int u, int v) { int ru = find(u); int rv = find(v); if (ru == rv) return; // 已经在同一个集合里 father[rv] = ru; // 让 rv 的父节点变成 ru }

这里有三个容易搞错的地方。第一，为什么 find 两次？因为 u 和 v 本身不一定是根，直接让 father[u] = v 只是局部移动。第二，为什么判断 ru == rv 就 return？说明 u 和 v 已经连通，再加这条边也不会带来新的连通信息。第三，father[rv] = ru 和 father[ru] = rv 有区别吗？从“是否连通”的角度看没有区别，但从树的平衡性看差别不小，这就是按秩合并要解决的问题。

2.4 isSame：两个节点是否在同一集合，本质是比较根

并查集最常见的查询函数：

bool isSame(int u, int v) { return find(u) == find(v); }

就这一行。为什么“根相同”等价于“连通”？因为在无向图里，每条边被 join 之后，所有节点最终被合并成若干个连通分量，每个连通分量只有一个根。如果两个节点的根相同，说明它们属于同一个连通分量，自然存在一条路径。反过来，根不同就必然不连通。

我学到这里时有过一个困惑：如果两棵树形态不一样，根明明相同，会不会路径已经被“更新”没了？不会。并查集只关心集合归属，不负责记录路径本身。它回答的永远是“能不能到”，而不是“怎么到”。

3. “寻找存在的路径”完整拆解：从读题到 AC

3.1 题目到底让你干什么

原题描述大致是这样的：给定一个包含 n 个节点的无向图，节点编号从 1 到 n，再给出 m 条边，每条边连接两个节点 u 和 v。最后给出起点 s 和终点 t，如果 s 和 t 之间存在路径，输出 1，否则输出 0。

需要注意的点是：这是无向图，所以 (u, v) 和 (v, u) 是等价的；不需要计算最短路径，存在即可；如果 s == t，那么路径长度为 0，也属于存在路径，应该输出 1。

读到这里，你应该已经发现：题目给的所有输入，几乎就是并查集初始化、合并、查询的标准流程。所以这不是一道需要奇技淫巧的题，而是让你检验自己是否真正理解了并查集的三个函数。

3.2 ACM 模式下的输入处理

很多刷题网站要求自己处理输入，代码随想录训练营也偏好在本地编译器里跑通后再提交。所以第一步要想清楚输入格式：

第一行：n m 接下来 m 行：每行两个整数 u v，表示 u 和 v 之间有一条边 最后一行：s t

我一开始犯过一个低错：把 m 条边读完以后，用 while (m--) 循环，结果后续还要用 m 统计信息，导致数据错乱。正确做法是先把 m 存到变量里，或者直接 while (m--) 且后面不再用 m。这种细节在本地能跑通、提交却超时或答案错误的情况里很常见。

3.3 完整 C++ 题解与逐段注释

#include <iostream> #include <vector> using namespace std; vector<int> father; // 初始化：n 个节点，每个节点的父节点是自己 void init(int n) { father.resize(n + 1); for (int i = 1; i <= n; i++) { father[i] = i; } } // 查找根节点 + 路径压缩 int find(int u) { if (father[u] == u) return u; return father[u] = find(father[u]); } // 合并两个节点所在的集合 void join(int u, int v) { int ru = find(u); int rv = find(v); if (ru == rv) return; father[rv] = ru; } // 判断两个节点是否连通 bool isSame(int u, int v) { return find(u) == find(v); } int main() { int n, m; cin >> n >> m; init(n); while (m--) { int u, v; cin >> u >> v; join(u, v); // 无向边只需要 join 一次 } int s, t; cin >> s >> t; if (isSame(s, t)) { cout << 1 << endl; } else { cout << 0 << endl; } return 0; }

这段代码已经包含了路径压缩，也就是 find 里的递归改写。为什么这里就加上？因为这道题虽然只有一次查询，但合并过程中树可能不断加深，如果不压缩，极端情况下 find 会退化得非常慢。学并查集的第一天就训练自己写路径压缩，后面遇到更复杂的题就不会漏掉这个优化。

3.4 从理论到落地之间的一层窗户纸

我第一次写这道题时有个疑惑：为什么 join 之后不需要根据边再做什么处理？比如会不会存在两条边交叉的情况？其实并查集不关心边的顺序，它只把“连通关系”逐步累积。无论先 join (1,2) 再 join (2,3)，还是先 join (2,3) 再 join (1,2)，最终 1、2、3 都会被合并到同一个集合里。这就是“并查集对动态加边非常友好”的原因。

如果用 DFS 做这题，你会发现代码要比并查集长不少：要建邻接表、要写 visited 数组、要递归搜索。而并查集只维护一个一维数组，就能回答同样的问题。这也是为什么把它放在图论的“开胃菜”位置——它让你提前感受“换一种数据结构，复杂度能差多少”。

4. 优化细节决定成败：路径压缩、按秩合并与常见误区

4.1 路径压缩：find 里多写一行，树直接变矮

朴素 find 的问题在于树可能退化成链表。解决办法是：在递归返回的途中，把沿途所有节点的父节点直接改成根节点。代码就是在原有递归基础上加一层“赋值”：

int find(int u) { if (father[u] == u) return u; return father[u] = find(father[u]); }

假设有一条链 1 -> 2 -> 3 -> 4，其中 4 是根。调用 find(1) 时，递归先到底层找到 4，然后回溯过程中依次执行 father[3] = 4, father[2] = 4, father[1] = 4。一次 find 之后，整条链变成了 1、2、3 都直接指向 4 的“菊花状”结构。之后再查任何一个节点，一步就能到达根。

如果担心递归深度太大导致爆栈，可以用迭代版路径压缩：

int find(int u) { while (u != father[u]) { father[u] = father[father[u]]; // 隔代提升，也算压缩 u = father[u]; } return u; }

这种写法在工程上更稳，但竞赛中递归版因为简短更常用。你只要记住：写递归版时，一定要把返回值赋给 father[u]，否则路径压缩不会生效。

4.2 按秩合并：合并前比一比树的高度

前面提到 father[rv] = ru 和 father[ru] = rv 都能合并，但如果总是把高树挂到低树上，树的高度会慢慢失控。按秩合并的思路是：用 rank 数组记录每棵树的“高度”，合并时让矮树的根指向高树的根。

vector<int> rankv; void initRank(int n) { rankv.resize(n + 1, 1); } void joinByRank(int u, int v) { int ru = find(u); int rv = find(v); if (ru == rv) return; if (rankv[ru] < rankv[rv]) { father[ru] = rv; } else if (rankv[ru] > rankv[rv]) { father[rv] = ru; } else { father[rv] = ru; rankv[ru]++; } }

这里 rank 初值设为 1 表示每棵树初始高度为 1。只有当两棵树高度相等时，合并后的根节点高度才会加 1。按秩合并单独使用，就能把树高控制在 O(log n) 级别；再配合路径压缩，整体复杂度可以认为是“反阿克曼函数”，在竞赛场景中你可以放心当成 O(1)。

实践中很多教材会两种优化一起讲，但题目大多只靠路径压缩也能过。按秩合并的价值更多在于：当你处理大规模数据、不想依赖递归深度、或需要严格分析复杂度时，它是更稳妥的选择。

4.3 这些坑我基本都踩过，列出来省你几小时

第一，编号从 1 开始却把数组开成 n。如果节点编号到 n，father[n] 就会越界。起步就把 init 里的 resize(n + 1) 写好。第二，m 条边可能为 0，输入里没有边只有最后一行 s t，此时 s 和 t 不连通，除非 s == t。代码里 while(m--) 能自然处理 m=0 的情况。第三，重复边和自环不需要特殊处理。join 内部会先判断根是否相同，相同就直接 return，所以多余边不会造成错误。第四，输出要求是换行后的 1 或 0，很多 OJ 对空格不敏感，但养成 cout << 1 << endl 的习惯总不会错。

还有一个隐藏点：如果 s 和 t 相等，直接输出 1。因为并查集里 find(s) == find(t) 必然成立——同一个节点当然和自己连通。这个边界不要漏掉。

4.4 复杂度直觉：为什么说它“几乎 O(1)”

没有优化的并查集最坏情况确实能达到 O(n)，但加上路径压缩后，find 的均摊复杂度急剧下降。严谨地说，同时使用路径压缩和按秩合并时，n 次操作的总复杂度是 O(n α(n))，其中 α(n) 是反阿克曼函数。这个函数增长极其缓慢：n 取宇宙原子数量级别，α(n) 也不超过 5。所以写成“均摊 O(1)”并不夸张。

不要被“反阿克曼函数”这个名词吓到。你可以这样理解：经过路径压缩后，绝大多数节点都直接指向根，一次 find 基本就是“看一眼父节点是不是自己”。即使偶尔碰到一条没压缩过的路径，查询成本也会在后续操作中被摊薄。这就是它适合处理海量连通性查询的根本原因。

5. 打卡之后还能往哪走：连通块、Kruskal 与更多变体

5.1 统计集合个数：一张图里有几个“帮派”

“寻找存在的路径”只问两个点是否连通，但并查集最常见的延伸，是一口气统计整张图有多少个连通分量。做法很简单：遍历所有节点，数一数有多少个节点的根是自己。

int count = 0; for (int i = 1; i <= n; i++) { if (find(i) == i) count++; }

注意这里一定要调用 find(i) 而不是直接判断 father[i] == i。原因在于，路径压缩通常在 find 过程中才发生，如果某些节点的 father 还停留在“父亲是中间节点”的状态，直接比较 father[i] 会漏数。先 find 一次，把整棵树都压扁，再判断根，结果才准确。

这类题最常见的变体就是“省份数量”：n 个城市，给出一个邻接矩阵，问有多少个省份。本质上就是统计连通分量个数。把矩阵里为 1 的格子当成边，套用上面代码即可。

5.2 Kruskal 最小生成树：并查集最重要的工业级应用

如果并查集只能判断连通性，它还不至于成为图论里的“基础工具”。它真正的爆发点在于 Kruskal 算法——求最小生成树。

Kruskal 的思路是：把所有边按权重从小到大排序，然后依次尝试加入每条边。加入前用并查集判断这条边的两个端点是否已经连通，如果连通就跳过，否则就加入并合并。判断“是否连通”正是并查集的看家本领。

sort(edges.begin(), edges.end(), cmp); int total = 0; for (auto &e : edges) { if (!isSame(e.u, e.v)) { join(e.u, e.v); total += e.w; } }

这个场景里，并查集不是查“路径存不存在”，而是查“加上这条边会不会形成环”。背后的逻辑是：如果 u 和 v 已经连通，再加一条边必然产生环。所以并查集天然适合做环检测，这一点在“冗余连接”这道题里也会反复用到。

5.3 带权并查集：从“是否连通”升级到“关系方向”

如果并查集只存父节点，那就只能回答 0/1 的连通性问题。但很多现实问题需要额外记录节点之间的关系，比如“u 比 v 大多少”“u 和 v 是同类还是异类”。这时就要用到带权并查集：每个节点除了记录父节点，还记录到父节点的权值。

带权并查集的核心是 find 递归时的权值累加和路径压缩时的权值更新。它比基础并查集难一个量级，但底层仍然是你今天学的这三个函数。如果你打卡进度允许，学完基础后花一天啃带权并查集，很多区间合并、食物链这类题就能顺手解决。

5.4 我的刷题建议与个人体会

这里想分享一点我在训练营过程中的真实感受。并查集这个算法，代码量极短，但特别容易出错的地方恰恰是“太短导致你以为不用动脑”。我建议你学完今天内容后，先别急着刷难题，把三个函数默写在纸上，推演一遍合并过程。然后做三道题巩固：一道基础判断连通（比如今天的寻找存在的路径），一道统计连通块（省份数量），一道环检测（冗余连接）。这三类题吃透，并查集的基础你就彻底拿下了。

我自己学下来最大的体会是：并查集把“图连通性”问题从图论领域抽离成了一个“集合归属”问题。理解了这个抽离过程，再回头看 DFS/BFS，你不会觉得它们被替代，而是会更清楚它们各自的定位——搜索负责给你路径，并查集负责给你关系。这种“换个角度看同一件事”的能力，可能比算法本身更能帮我们在后续刷题里走得更远。啰嗦了不少，但希望对正在打卡第 59 天的你有点帮助。