说起并查集很多人第一个正经练手的题就是洛谷的 P1536 村村通。这题背景特别朴素某市统计了现有城镇道路问最少还要修几条路才能让任意两个城镇都能间接到达。说白了就是给你一张图里面有些点已经连成几块问还要补几条边才能让整张图变成一个连通块。我这些年带新人刷题每次讲完并查集基本都拿这道题当验收题。它代码量不大但把并查集的初始化、查找、合并三个核心操作全过了一遍而且特别能检验你是不是真理解了“连通分量”而不是只会套模板。这题的另一个好处是天然有多组数据能顺带练一练输入输出和数组重置的细节。不管你是刚学数据结构的新手还是想快速复习并查集的老人这题都非常值得认真过一遍。下面我就把这道题的建模思路、并查集原理、完整代码以及我刷题时踩过的坑一次性说清楚。1. 题目场景与建模把修路问题变成数连通块1.1 从“村村通”背景到图论模型我们先别急着写代码先做一件最重要的事把题目翻译成图论语言。城镇就是图的顶点城镇之间的道路就是图的边。“两个城镇之间可以间接到达”的意思是它们在图里属于同一个连通分量。于是这个问题就变成了当前这张无向图有多少个连通分量如果答案是 k那最少还要修 k-1 条路。为什么是 k-1这里可以这样想一条新路最多把两个本来不连通的连通分量“合并”成一个。假设现在有 k 个互相独立的连通块每修一条路就只能让两个块合并块的数量减一。要让 k 个块最终变成 1 个块最理想的情况就是修 k-1 条路刚好把所有块串成一串。这是最优的下界也一定能达到因为你随便找两个连通分量之间加一条边就行。举个例子输入数据是4 2 1 3 4 34 个城镇2 条路1 连 34 连 3。所以 1、3、4 这三个点就在同一个连通分量里孤立的是 2 号城镇。图里一共有 2 个连通分量答案就是 2 - 1 1。这个和题目样例的输出完全一致。1.2 为什么这题用 BFS/DFS 能做但不推荐很多新手第一反应是那我对每个点做一遍 BFS 或 DFS看能访问到哪些点这不也能数出来连通分量吗确实能。图很小的时候BFS/DFS 的复杂度 O(NM) 也完全够用甚至代码写起来也不算太难。但这道题有一个很现实的问题它是多组数据每一组都要重新建图、重新清空 visited 数组。如果数据组数多图又比较稀疏反复建邻接表会显得有些臃肿。更重要的是BFS/DFS 只能处理静态图也就是边全部给完以后一次性遍历。而并查集不一样它对边的处理是“增量式”的来一条边我就合并一次随时可以回答“当前已经形成了多少个连通块”。这个特性在后续的最小生成树、判环、离线动态连通性等问题里都非常关键。所以我的建议是连通分量计数这种活儿优先用并查集不要养成动不动就开邻接矩阵的习惯。尤其是像计算“还差几条边”这种问题并查集直接维护一个连通块计数器边读边算干净利落。2. 并查集的三个基本操作与优化从数组到路径压缩2.1 parent 数组与 find/union 的核心逻辑并查集这东西说穿了就是一个数组。parent[i]表示 i 号节点的父节点是谁。一开始每个人都指向自己也就是每个点自成一个连通块。for (int i 1; i n; i) parent[i] i;然后我们定义两个操作find(x)找到 x 所在集合的“代表元素”也就是根节点。unite(a, b)把 a 和 b 所在的集合合并成一个合并前先找到两个根如果根相同说明已经在同一个连通块里就不需要合并。用生活化的说法每个连通块里有一个“话事人”你想知道两个村庄是不是一伙的就看它们的话事人是不是同一个人。修了一条新路相当于两个村庄结盟话事人统一。对应的代码长这样int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } bool unite(int a, int b) { int ra find(a); int rb find(b); if (ra rb) return false; parent[ra] rb; return true; }注意unite的返回值。很多人写并查集根本不在乎返回值但在这道题里这个返回值非常有用只有当两个点原本不在同一个连通块时连通块数量才需要减一。如果它们本来就连通你再加一条边对连通块数量没有任何影响。2.2 路径压缩别让你的树变成一根面条前面这个find是递归写法它做了一件重要的事路径压缩。当你在查找 x 的根时递归返回的过程中会让沿途经过的所有节点都直接指向根节点。这样下次再查这些节点的时候基本一步就能到位。如果不做路径压缩纯粹的并查集在最坏情况下会退化成一条很长的链表。想象一下每次合并都让一棵树的根挂到另一棵树的根下面而且方向都一致那么树高会接近点数。查找时就得一层一层往上爬复杂度从近似常数直接退化成 O(N)。路径压缩就是把这个隐患消除的关键优化。还有一种优化叫按秩合并也就是让高度小的树挂到高度大的树下面。实际做题时绝大多数人只写路径压缩就够用了因为路径压缩单独使用时的均摊复杂度已经低到接近常数。不过我愿意把按秩合并也当成一个习惯来写尤其在处理大规模数据时更稳妥。2.3 均摊复杂度为什么并查集可以当作 O(1) 用这里可以简单说一句复杂度结论同时使用路径压缩和按秩合并的并查集单次 find/unite 操作的均摊时间复杂度是 O(α(N))其中 α 是反阿克曼函数。α(N) 的增长极慢在人类能遇到的数据规模内几乎可以当成常数。这也是为什么并查集在各种算法竞赛里被称为“性价比之王”。它代码量极小却能解决很多看似复杂的问题。就拿 P1536 来说整道题的复杂度是 O(N M·α(N))空间复杂度 O(N)。哪怕 N 是十万、百万级别跑起来也毫无压力。不过这里顺便提醒一句在大多数 OI/ACM 场景下只做路径压缩也已经足够快真正需要按秩合并的场合其实不多。你真正要警惕的不是复杂度而是把find写错或者合并方向搞反。3. 代码实现C 与 Python 各一份附完整注释3.1 算法主流程梳理写代码之前先把整体流程理一遍。读入 n 和 m如果 n 为 0 则整个程序结束。初始化 parent 数组让每个节点指向自己。维护一个计数器 cnt初始值为 n表示当前有 n 个独立的连通块。依次读入 m 条边对每条边执行 unite。如果 unite 返回 true说明确实把两个不同连通块合并了让 cnt--。全部边处理完之后cnt 就是图中连通分量的个数答案就是 cnt - 1。输出答案继续读下一组数据。计数器这个技巧值得重点记一下。它和“最后遍历所有点统计根节点个数”的效果一样但省掉了一次完整的遍历和去重操作。3.2 C 完整实现#include bits/stdc.h using namespace std; const int MAXN 1005; int parent[MAXN]; int find(int x) { // 递归查找根节点路径压缩让沿途节点直接指向根 if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } bool unite(int a, int b) { int ra find(a); int rb find(b); if (ra rb) return false; // 已在同一连通块合并无效 parent[ra] rb; // 把 ra 所在树的根挂到 rb 下 return true; // 合并成功连通块数量减一 } int main() { int n, m; while (scanf(%d, n) 1 n ! 0) { scanf(%d, m); // 初始化每个城镇都是独立的连通块 for (int i 1; i n; i) { parent[i] i; } int cnt n; // 当前连通块数量 for (int i 0; i m; i) { int a, b; scanf(%d%d, a, b); if (unite(a, b)) { cnt--; } } printf(%d\n, cnt - 1); // 需要 cnt - 1 条新路 } return 0; }这里scanf的返回值是一个容易被忽略的小细节while (scanf(%d, n) 1 n ! 0)既能判断是否读到了有效整数又能为多组数据读取提供退出条件。如果某个测试文件末尾后面还有空白字符这种写法不会把空白字符当作数字读进来。3.3 Python 完整实现Python 写并查集有一个需要注意的点递归深度。如果 n 很大而且树退化成链递归版本可能直接爆栈。所以我推荐写迭代版的完全路径压缩。import sys def find(parent, x): # 第一遍循环找到根节点 root x while parent[root] ! root: root parent[root] # 第二遍循环把所有路径上的节点直接接到根上 while parent[x] ! x: nxt parent[x] parent[x] root x nxt return root def unite(parent, a, b): ra find(parent, a) rb find(parent, b) if ra rb: return False parent[ra] rb return True def solve(): data sys.stdin.read().strip().split() idx 0 out [] while idx len(data): n int(data[idx]) idx 1 if n 0: break m int(data[idx]) idx 1 parent list(range(n 1)) # parent[0..n]下标从 0 开始 cnt n for _ in range(m): a int(data[idx]) b int(data[idx 1]) idx 2 if unite(parent, a, b): cnt - 1 out.append(str(cnt - 1)) sys.stdout.write(\n.join(out)) if __name__ __main__: solve()Python 这份代码我习惯用sys.stdin.read().split()一次性读入全部数据。这种写法在处理多组数据、每组数据行数不一的时候尤其方便因为不需要逐行处理逻辑只要维护一个指针逐步读取整数即可。注意城镇编号是从 1 开始的所以parent数组长度设为n1下标 0 不用。3.4 统计连通块的两种写法对比除了维护 cnt 计数器另一种常见的做法是处理完所有边之后把所有find(i)的结果放进一个 set 里最后输出set.size() - 1。int cnt 0; setint roots; for (int i 1; i n; i) { roots.insert(find(i)); } printf(%d\n, (int)roots.size() - 1);两种写法都能 AC但计数器写法更省空间也少一次循环在数据集特别大的时候优势明显。更重要的是它逼着你理解“合并成功才减一”这个语义不容易在统计时犯错。新手我不建议一步到位用计数器可以先写 set 版验证自己对连通块数量的理解再改成计数器版这样记忆更深刻。4. 刷这道题容易卡住的细节与我的排错经验4.1 多组输入时数组没重置的翻车现场这是 P1536 最容易踩的坑没有之一。题目是多组数据每一轮都要重新读入 n 和 m然后重新初始化 parent。很多刚接触多组数据题目的同学要么忘记重置要么只在最开始统一初始化了一次导致第二组数据进来时点的父节点还是上一组数据留下的旧关系。一眼看过去代码逻辑好像没问题样例可能也能过但交上去就 WA。原因就是合并结果在不同数据组之间污染了。任何多组数据的题我建议都养成分步骤检查的习惯一次循环代表一组完整数据循环内部第一件事就是重置所有全局状态。4.2 unite 返回值和合并方向的小陷阱在 C 代码里我把unite设计成有返回值的函数返回 false 表示两个点原本就在同一个连通块返回 true 表示合并成功。新手经常犯两个错误。第一个错误合并前不判断根是否相同直接写parent[a] b。这会造成严重的逻辑错误因为 a 和 b 不一定是各自连通块的根直接改父节点等于把一棵树里的某个内部节点连到另一个树上整棵树的结构就乱了。第二个错误合并时忘了让连通块计数器减一。计数器只在真正发生合并时变化不能对每条边都cnt--。我见过有人图省事直接在循环里无脑cnt--结果把答案数成了边数输出全是负数。4.3 递归 find 在极端情况下的爆栈风险C 路径压缩的递归写法本身没问题递归深度取决于树的当前高度。在极端测试数据下如果你没有路径压缩而且合并顺序又很毒树高可能达到 n这时候递归深度非常大轻则超时严重时直接段错误。Python 更要注意这个问题所以我的 Python 版本用了迭代式路径压缩。你没有必要追求代码看起来短稳定不出错才是最重要的。4.4 我调试这类题常用的三个测试用例以下这三组数据我建议每个写并查集连通性题的人都刻在脑子里只有一个点没有边1 0答案应该是 0。这一步能验证最小规模下的逻辑。所有点都没边比如5 0答案应该是 4。说明所有点都是独立连通块。所有点已经成环连通比如3 3加上1 2、2 3、1 3答案应该是 0。这能验证重复边和环不会让计数器多减。每次我改完并查集代码都会先用这三个用例跑一遍再拿题目样例验证。这样一旦有问题基本能迅速缩小范围到 find 或 unite 的逻辑上。5. 由“村村通”展开并查集的常见变体与下一步学习路线5.1 从数连通块到 Kruskal 最小生成树P1536 本质上是问“最少加几条边能让图连通”。如果你再进一步问“让图连通且总边权最小”那就变成最小生成树问题了。Kruskal 算法最核心的一步就是贪心选边但选边之前必须先判断这条边的两个端点是不是已经在同一个连通块里如果已经连通还选它就会成环。这个判断用的就是并查集。你只要把 P1536 吃透Kruskal 的代码其实只多了一个“边按权值排序”的过程剩下的合并逻辑几乎一模一样。5.2 无向图判环合并失败的边就是你想要的边还有一个非常实用的变体判断一张无向图里是否存在环。对每条边执行 unite如果某条边的两个端点已经在同一个连通块里说明这条边是多余边图里存在环。这在实际工程里也经常抽象出来用。比如检查一组网络设备之间的连接配置是否会形成环路或者判断一次数据库表结构迁移里的引用关系是否循环依赖。虽然真实系统比图论模型复杂得多但核心判环逻辑是同一套。5.3 离线动态连通性用“倒着做”的技巧再深一层有一个比较高级的技巧叫离线动态连通性。场景是给一张图然后依次删除若干条边每次删完问当前图有几个连通分量。删除边这个操作并查集不支持但如果你把询问离线读进来从最后一次删除开始倒推删除就变成了添加这时候并查集就又可以用了。这就是“倒着做”的思路。在一些复杂题里它结合线段树分治可以处理更困难的动态图问题不过现阶段你只需要记住这个思路的源头依然是并查集最基本的合并操作。5.4 推荐练习路径如果你刚刚打通 P1536下一步我建议按这个顺序练P1551 亲戚并查集最朴素的“查询是否属于同一集合”应用。P3367 并查集模板标准模板题适合把路径压缩和按秩合并都写熟。P3371/P3366 最小生成树从并查集过渡到 Kruskal。P1197 星球大战离线加边并查集的经典应用做完你对反向思路的理解会上一个台阶。这些题和 P1536 的代码结构非常接近区别只是场景和操作更丰富。你花一个下午认真刷完基本上并查集这个数据结构就算真正吃透了。最后再分享一个我个人的习惯做这种连通性题目我从来不会一上来就写代码而是在草稿纸上画几个圆圈代表点按输入把已知的边连上线数一数目前有几个独立的“小岛”。P1536 这道题很多同学卡住不是因为不会并查集而是根本没想明白“最少修路数连通分量数-1”。想明白这一点代码基本就是在套模板了。如果你还在学并查集我建议把上面 C 和 Python 两份代码都亲手敲一遍再把 cnt 计数改成 set 统计根节点对比一下输出有没有区别。这种动手验证过程比看十篇题解都管用。