1. 题目到底在说什么从生活场景到图论模型1.1 一读题面先别急着写代码题目给出了两个整数n和mn表示村庄数量m表示现有道路数量。接下来的m行每行给出两个整数a和b表示村庄a和村庄b之间已经有一条路了。注意这里的“路”是双向的a能到bb也就能到a所以这是一张无向图。很多新手拿到题先想的是“我要怎么建图邻接矩阵还是邻接表”对于这道题来说其实根本不需要显式地把图存下来你只需要维护村庄之间的连通关系就够了。这就是并查集的用武之地不需要知道具体路径长什么样只需要知道两个点是否在同一个连通集合里。如果把村庄抽象成点道路抽象成边那整个问题就是有一个无向图图里可能有好几个连通分量也就是几片互不相连的“孤岛”现在要修新路把所有连通分量连成一个整体。需要修的路的数量就是连通分量个数减一。理解到这层题目基本就转化成了“数连通分量个数”这个思路是整道题的题眼。1.2 为什么答案是连通分量减一而不是其他这里面的数学直觉很朴素。假设当前图里有 k 个连通分量你每修一条新路最多只能把两个连通分量合并成一个。也就是说每修一条路连通分量数量最多减少 1。要让 k 变成 1最少需要 k-1 条新路。那能不能用更少的路、一条路一次串起三个分量不可能一条无向边只有两个端点一条路只能落在两个村庄之间所以它最多把两个分量连通。这是最朴素的“边数下限”论证。另一方面k-1 条路一定够用你随便挑一个连通分量当作“核心”然后在它和其余每个连通分量之间各修一条路就全通了。所以最少就是 k-1不多不少。这个推导过程值得多说一句因为我在新手阶段就是卡在这我老想着“万一某条新路能同时连接多个不连通的部分呢”后来才反应过来边只有两个端点这是图论里最基础也最容易忽略的约束。想清楚这一点代码怎么写反而不难了。2. 并查集这道题背后的不二主角2.1 并查集到底在干什么并查集是一种管理元素分组的数据结构核心就两个操作查找Find和合并Union。查找是找某个元素所在集合的根节点顺便还能做路径压缩合并是把两个不同集合合并成一个。通常我们还会维护一个“集合数量”或者“每个集合的大小”方便统计连通分量个数。拿“村村通”来说一开始每个村庄都单独算一个集合。读入一条已经修好的路 (a, b)就把 a 和 b 所在的两个集合合并。所有边读完后统计现在还有几个集合答案就是集合数量减一。整个过程非常直观几乎可以照着并查集模板直接抄。很多文章讲并查集会直接甩模板然后说“背下来就行”但我个人不太建议这么学。你得先理解一个关键点并查集并不是真的把“图”结构存下来了它只是记录了“谁和谁是同一组”。对于只关心连通性、不关心路径细节的问题这种抽象恰好够用。这也是为什么它在最小生成树Kruskal算法、网格连通性判断、朋友圈划分等场景里都是标配。2.2 路径压缩和按秩合并到底要不要写网上关于并查集的模板有两种常见写法一种是只做路径压缩另一种是路径压缩加按秩合并。对 P1536 这种数据规模来说其实只做路径压缩就完全够用运行时间漂亮得很。但作为学习我还是建议把按秩合并也理解透。所谓路径压缩就是在 find 的过程中顺手让路径上的所有节点直接指向根节点。这样下次再查这些节点时就能一步到位。复杂度的神奇之处在于加入了路径压缩之后并查集的单次操作复杂度可以近似看作常数级别准确说是反阿克曼函数这个函数增长慢到离谱基本可以认为是 O(1)。按秩合并则是说合并时把“浅的树”接到“深的树”下面避免树越来越深。如果只做路径压缩不按秩合并理论上会有一些特殊构造让复杂度退化但实际题目基本遇不到。这道题的数据范围我记得非常宽松n 好像是不超过 1000m 也不大所以怎么写都能过。不过别因为“能过”就只写一套面试或者实际工程里理解这两种优化能帮你应对更复杂的需求。3. 手把手拆解并查集代码实现3.1 C 实现和关键细节我平常用 C 写这种题比较多模板基本长这样#include iostream using namespace std; const int MAXN 1005; int fa[MAXN]; void init(int n) { for (int i 1; i n; i) { fa[i] i; } } int find(int x) { if (fa[x] x) { return x; } return fa[x] find(fa[x]); // 路径压缩 } void unite(int a, int b) { int ra find(a); int rb find(b); if (ra ! rb) { fa[ra] rb; } } int main() { int n, m; while (cin n m) { if (n 0) break; init(n); for (int i 0; i m; i) { int a, b; cin a b; unite(a, b); } int cnt 0; for (int i 1; i n; i) { if (fa[i] i) { cnt; } } cout cnt - 1 endl; } return 0; }有几个点值得单独拿出来说。第一输入有几个测试用例直到读到 n 0 才结束这是题目固定的输入格式别漏了。第二统计连通分量个数的时候我直接数 fa[i] i 的个数也就是“有多少个根节点”。这里有个前提就是我 init 的时候让每个 fa[i] i并且路径压缩不会改变根节点自身指向自己的性质所以这个统计方式是安全且稳定的。第三注意这里合并的时候我是直接 fa[ra] rb没有判断秩。对于这个题目规模完全没问题。如果你用递归 find在数据很大时小心爆栈可以考虑改成迭代写法。虽然本题不会但养成这个意识没坏处。3.2 Python 实现用竞赛题练工程手感如果你不搞 CPython 写这道题也很快。用列表存父节点代码是下面这样import sys def find(x): while fa[x] ! x: fa[x] fa[fa[x]] # 路径压缩 x fa[x] return x def unite(a, b): ra find(a) rb find(b) if ra ! rb: fa[ra] rb def solve(): data sys.stdin.read().strip().split() idx 0 out [] while idx len(data): n int(data[idx]); idx 1 m int(data[idx]); idx 1 if n 0: break global fa fa list(range(n 1)) for _ in range(m): a int(data[idx]); idx 1 b int(data[idx]); idx 1 unite(a, b) cnt sum(1 for i in range(1, n 1) if fa[i] i) out.append(str(cnt - 1)) sys.stdout.write(\n.join(out)) if __name__ __main__: solve()这里我用了一个小技巧把整个输入一次性读进来再切分避免一行行读导致的速度损失。虽然这题数据量小但竞赛里养成“快速读入”的习惯没坏处。find 我用的是迭代写法同时做了路径压缩在这个写法里 fa[x] fa[fa[x]] 的意思是让 x 跳到它父节点的父节点相当于压缩了一半的路径。如果追求极致也可以写成完整的递归压缩但对这个题来说意义不大。3.3 一个坑节点的编号范围可能不是连续的这是我最想提醒的一点。题目说的是 n 个村庄编号一般从 1 到 n。但有些同学会把数组开成 n 个也就是下标从 0 到 n-1结果读入 a n 的时候直接越界。还有变体题里可能出现某些编号根本没有边连接但依然算一个单独连通块所以统计时要遍历 1 到 n 的全部编号而不是只统计出现过的点。我见过不少人在这里翻车只把“在边中出现过的点”拿去判连通块数量结果没在边里出现的孤立点全被漏掉了导致答案偏小。说白了只要题目声明了有 n 个村庄那就每个编号都是一个“点”不管它有没有出现在输入里。这种细节才是决定一道题能不能一次 AC 的关键。4. 从“村村通”到工程实践并查集还能干什么4.1 最小生成树 Kruskal 算法里的并查集很多刷题的人认识并查集其实是从 Kruskal 算法开始的。Kruskal 的做法是把所有边按权值排序然后从小到大一条条尝试加入生成树。加入之前先判断两个端点是不是已经在同一个集合里如果是说明加上这条边会成环得跳过如果不是就合并同时把边权累加进答案。这个过程里“判断成环”就是并查集最典型的应用场景。回到“村村通”如果你把“已有道路”想象成权值为 0 的边把“可能要修的新路”想象成权值为 1 的边那这个问题其实可以归约成一种特殊的最小生成树问题已经存在大量免费边剩下的边权值全部为 1求最小生成树的总权值。这样理解的话答案“连通分量数减一”就解释得更顺了。4.2 动态连通性网络、朋友圈、集群节点工程里还有一种更常见的需求动态连通性判断。比如服务器集群里有几台机器要互相通信新加了一条链路就要更新连通关系比如社交网络里两个人是不是同一个圈子再比如地图上两块区域是否已经打通。这类问题如果每次实时搜索所有路径代价很高而并查集几乎是以 O(1) 的均摊代价维护“是否连通”这个信息。我以前参与过一个内部系统里面需要判断两个配置文件是否属于同一棵依赖树。最初方案是每次查都做 DFS后来数据量大了才发现不对劲改成并查集之后合并和查询都快了几个数量级。虽然场景里不会有“路径压缩”这么学术的名字但本质就是一个东西。这也解释了为什么竞赛题刷多了写业务代码时思路会开阔很多。4.3 “合并集合”不等于“合并所有边”一个容易糊涂的点有同学可能会问既然并查集讲究合并那我把所有边都 unite 一遍之后是不是就已经把所有能连的村庄连成一个大集合了答案是肯定的这也是核心。但要注意“能连的”指的是已有道路形成的连通关系并不会因为“未来可能修的路”而提前连通。后面要修多少条路是统计完现有集合数量之后才计算的。这个边界如果没想清楚很容易写出“每读入一条边先判断、再决定是否计数”的错误逻辑。正确顺序是先把所有已有边全部合并完之后再去数集合数量。不要边读边统计除非你能保证统计逻辑不依赖后续边但那样既要维护额外变量又容易出错不如“先合并再统计”来得干脆。5. 完整梳理一遍题目思路从读题到 AC 的思维路径5.1 我建议按这个顺序去思考任何连通性题第一步把所有对象看成点。这里就是 n 个村庄。第二步看清边是什么。这里就是 m 条已有道路。第三步判断问题问的是“连通块数量”还是“两点是否可达”还是“最小连接代价”。P1536 问的是“还要多少条边让整张图连通”本质上就是数连通块。第四步选数据结构。只关心连通关系不关心具体路径选并查集。第五步代码实现。初始化、合并、统计、输出。这套思考顺序几乎可以套用到所有并查集相关的题上从“朋友圈”到“省份数量”再到“冗余连接”都是同一个套路。学会这种“先把问题抽象成图再选择合适的数据结构”的思维比记住某道题的具体代码重要得多。5.2 用一组数据手动推演一遍假设输入是4 2 1 2 3 4 0 0n4m2。一开始 1、2、3、4 各自独立。读入 (1,2) 后1 和 2 合并成一个集合读入 (3,4) 后3 和 4 合并成一个集合。此时集合数量是 2它们是 {1,2} 和 {3,4}。要让所有村庄连通需要 2-11 条路比如在 2 和 3 之间修一条四个村庄就全通了。再看一个稍微复杂点的例子5 3 1 2 2 3 4 5 0 01、2、3 通过两条边连成一体4、5 连成一体剩下没有出现在边里的村庄……哦这里没有但如果 n 改成 6再多一个 6那 6 就是一个单独集合。总共 3 个集合答案是 2。这个例子可以帮你理解“没出现在边里的点也要算一个集合”。说到手动推演我习惯在草稿纸上把每个集合的“根节点”写出来然后每次合并就画一个箭头。你会发现并查集明明叫“树”但操作起来更像在维护一个“森林”每棵树是一个集合根是集合的代言人。最终要修的路线数量就是森林里的树数量减一。5.3 关于时间复杂度补一刀并查集单次 find 和 unite 近似 O(1)所以整个程序的复杂度基本是 O((nm)·α(n))α(n) 是反阿克曼函数。对本题数据来说完全不用担心超时。真正值得注意的是输入输出方式C 用 cin/cout 也不慢但如果遇到更大数据量的变体建议加 ios::sync_with_stdio(false) 和 cin.tie(nullptr)或者干脆用 scanf/printf。Python 则推荐一次性读取所有数据然后再处理。6. 踩坑记录我在 P1536 上犯过的错和排查思路6.1 忘记处理多组输入直接 Wrong Answer这道题是多组测试数据最后一组是“0 0”。我第一次写的时候只处理了一组输入就 return 了结果样例过了一提交就 WA。后来仔细读题才发现问题。很多“水题”其实是输在上手习惯上而不是算法本身。所以拿到题目第一件事应该是把输入输出格式完全搞清楚。6.2 数组越界开小了我刚开始开数组时习惯用 n5 大小这题是没问题的。但假如题目里村庄编号不是 1 到 n而是离散的大编号比如 1 和 100000那我开 1005 的数组就会越界。解决方案有两种一种是根据编号范围开足够大的数组另一种是用哈希表 / map 做离散化。P1536 虽然用不到但在其他变体里很常见。6.3 统计根节点的方式fa[i] i 不总是对的如果初始化时所有 fa[i] i并且所有合并都通过 find 走到根那统计 fa[i] i 就是对的。但有人会写出“把子节点指向父节点但不保证根节点指向自己”的写法比如合并时只改了非根节点的 fa那就乱了。规范做法是init 时 fa[i]iunite 时把其中一个根接到另一个根find 做路径压缩。只要这三个点都规范统计就很安全。我在排查这类问题时习惯写一个 debug 函数把 fa 数组完整打印出来看看哪些点指向自己。比如 n5 时打印出 fa [0,1,1,3,3,5]就能一眼看出根节点是 1、3、5集合数量是 3。这个小技巧在正式比赛里也很有用尤其当你确认逻辑没错却老 AC 不了的时候先别怀疑人生先打印出来看数据。6.4 合并方向的坑fa[ra] rb 还是 fa[rb] ra这两种写法一个意思只要保证把一边的根指向另一边的根即可。但如果写成 fa[a] b 而不是 fa[find(a)] find(b)那就漏掉了路径压缩可能导致某个点没被真正合并到根上。后面统计时就会多算集合。所以合并前一定要 find 两个点拿到根再操作。这是新手最常见的 bug没有之一。7. 这题还能怎么变着玩从“村村通”到更复杂的模型7.1 变体一带权并查集如果题目里加一个要求不仅要知道两个村庄是否连通还想知道两个村庄之间的“距离”或“关系”那就需要用带权并查集。每个节点除了指向父节点还要记录一个到父节点的权值。这个权值可以是路径长度、逻辑关系的偏移量甚至是模运算下的差值。带权并查集在“食物链”“银河英雄传说”这类经典题里是常客。7.2 变体二反向并查集 / 删边问题有些题目会问“如果某条路被切断了连通性会产生什么影响”这种动态删边问题如果用并查集正着做很难因为并查集只支持合并、不支持删除。但可以换个思路离线处理倒着来。先把所有要删的边都删掉之后的状态建好然后从最后一步向前逐步“加回”边每次加边都对应一次合并。这就是所谓离线反向并查集。P1536 的“修路”方向正好和它相反但底层结构是同一套。7.3 变体三最小生成树变体如果每条新修的路有各自的成本而不是统一的“1 条路”那问题就升级成了“最小成本让所有村庄连通”。Kruskal 算法直接做就行。换句话说P1536 其实是 Kruskal 的一个特例把所有候选边的权值都视为 1。理解了这一点以后看到“最少需要修几条/多少钱”这类题就能快速归类。8. 日常做题的几点体会说回到最开头我为什么觉得 P1536 值得写一篇博客因为它的核心解题步骤极简但背后承载的知识点却是一条完整的链图的连通分量概念、并查集数据结构、反阿克曼函数带来的复杂度优势、以及把生活问题抽象成图论模型的能力。从学习的角度看性价比非常高。如果你现在正在刷题我的建议是不要急着看题解自己先动手写。哪怕写得又臭又长哪怕一开始只会用 BFS/DFS 去数连通块也要先写完。等你意识到“每次查询连通性都要重走一遍搜索也太麻烦了”你才能真正体会到并查集那种“用树根代表集合身份”的精妙。之后再去比较 BFS/DFS 和并查集两种写法的时间和空间开销收获会比直接背模板大很多。顺带说一句这道题用 BFS/DFS 也能做建邻接表从每个未访问的节点出发做遍历每次从未访问节点开启新遍历就说明发现了一个新的连通块最后连通块数量减一就是答案。但对于大规模数据并查集的空间开销更小写起来也更简洁。两者各有适用场景别觉得会一种就天下无敌。最后分享我在实际做题时的一个习惯AC 之后多回头想想如果 n 变成 10^5m 变成 10^6我的代码还能不能秒出如果答案是否定的说明还有优化空间。P1536 的并查集写法完全扛得住这种压力这也是我推荐新手认真掌握它的原因。希望这篇拆解能帮你在“村村通”这道题和大名鼎鼎的并查集之间建立起真正属于自己的连接。
