★ FEATURED ARTICLE 接手洛谷 P1536 村村通的人多半不是为了刷一道水题而是想找一个“把并查集彻底搞懂”的入口。这道题在国内 OJ 上被无数人翻过牌子核心就一句话并查集判连通块答案等于连通块数减一。但题解虽多很多代码要么没注释要么写法绕新手抄下来跑通就完事换个场景照样懵。所以这篇不打算复读官方的“并查集基本原理”而是从读题到建模从代码到调试把每个“为什么”都拆开讲清楚。你会看到我在现场是怎么想的哪些地方容易踩坑以及一份带详细注释、可以直接抄作业的 C 代码。适合刚学并查集、准备打基础算法题的人也适合那种看懂了模板但做题就卡壳的同学。1. 题目到底在讲什么先盘清楚需求再动手1.1 题意复述与输入输出细节题目背景非常接地气某地区有 n 个村庄修了一些路现在想再修几条路让任意两个村庄之间都能直接或间接互通。输入给的是 n 和 m接下来 m 行每行两个数表示两村庄之间已有一条路。n0 时结束。要求输出最少还需要修几条路。这里有个坑位你得先站稳题目说的“已有一条路”指的就是并查集里的“连通关系”。A 村和 B 村之间有路那 A 和 B 就是一个集合里的点子如果 C 村和 D 村有路D 又和 A 有路那四个村都在同一个连通块内。最终目标是把所有连通块连成一个大块最少要修的边数就取决于一开始分成了几块。输入规模不大n 最多 1000 左右m 随意边界条件就是 n0 终止。这道题的数据范围决定了我们不需要花哨算法O(n m α(n)) 的并查集就绰绰有余。但正因为数据小很多人才会忽略背后的大数据扩展性我建议从一开始就养成写路径压缩的习惯不然后面遇到百万级别的数据会吃亏。1.2 为什么答案等于“连通块数减一”这是整题最核心的推导也是很多人卡住的地方。先想一个重要事实n 个独立的点要连成一个整体最少需要 n-1 条边。你可以想象成 n 个人手拉手站成一排只要 n-1 次“牵手”动作就能串成一条链而一条链已经能让任意两人通过传递牵手互相联系。现在题目给了一部分初始道路这些路把某些点提前“牵”在了一起。于是场景变成假设你已经有 cnt 个“人团”每个团内部已经牵手ok但团和团之间还没连上。要让所有人都连成一个大整体你需要的边数就是 cnt-1——因为每修一条路最多只能把两个独立团合并成一个团合并 cnt 个团需要 cnt-1 次。这就是整个答案公式的来源统计并查集里有几个根节点然后输出根节点数减一。代码上就是对每个 i 执行 find(i)如果找到的根还是 i 自己说明它是一个独立的连通块代表cnt。1.3 一个看起来简单但容易踩的边界有的同学会问“那我直接把每个孤立点单独算一条路是不是也行”其实意思一样但要注意判断方式。常见写法是枚举 i统计 fa[i] i 的数量这依赖了路径压缩后每个连通块的根节点的 fa 指向自己。如果你并查集初始化时 fa[i] i并且所有操作都走 find那么这个统计是可靠的。但如果中途使用了“按秩合并”并且没有路径压缩彻底fa[i] i 的判断依然靠谱因为根节点总是指向自己。真正会出错的情况是你初始化时用了 fa[i] 0然后用 find 递归返回 0 作为根那统计方式就得改成判断 find(i) 是否等于某个固定哨兵值。为了省心我建议一律用“每个节点的父节点初始化为自己”这种写法统计和查错都直观。2. 并查集的底层原理与 C 实现细节2.1 三件套初始化、查找、合并并查集数据结构本质是一片森林fa[x] 表示 x 的父节点。一个集合的“代表”就是根节点。初始时每个节点自成一棵树fa[i] i。查找操作 find(x) 沿着父节点一路往上爬直到找到根合并操作 unite(x, y) 把两棵树的根连起来。这三件套构成并查集的核心村村通这道题只需要这三样。很多教材喜欢把并查集讲成“找朋友”“江湖门派”我个人觉得不要被这些故事带偏直接盯着森林和父节点数组建模就行。你心里有个数组知道每个元素向上指到谁做题时一切就清晰了。2.2 路径压缩一句话省下指数级时间find 操作如果不优化最坏情况下树退化成一条链查询一次就是 O(n)。路径压缩就是在递归查找根的过程中顺手把路径上所有节点的父节点直接改为根节点这样下次再查就是 O(1)。代码上只多了一行int find(int x) { if (fa[x] ! x) fa[x] find(fa[x]); return fa[x]; }你仔细品一品这行递归当 find(fa[x]) 返回来的时候fa[x] 已经变成了根节点再把 fa[x] 赋给当前 fa[x]于是这一整条路径上的所有点都被压平了。这个技巧在洛谷所有并查集题里几乎都是标配哪怕数据只有 1000我也劝你带上因为不费事而且能避免某些极端测试点。2.3 按秩合并选装的高端优化按秩合并的思路是把矮树接到高树上避免树高度增长过快。对于本题来说n 最大 1000纯路径压缩已经足够按秩合并写不写无所谓。但如果未来你要处理百万级节点我建议把秩也维护上。int rnk[1005]; void unite(int x, int y) { x find(x); y find(y); if (x y) return; if (rnk[x] rnk[y]) fa[x] y; else { fa[y] x; if (rnk[x] rnk[y]) rnk[x]; } }秩定义为树的最大深度近似值初始为 0 或 1 都行。注意合并时是根节点互相挂接不是普通节点。很多新手错在 unite(x, y) 里直接 fa[x] y没有先 find这样会把 x 这整棵子树挂到 y 上导致结构错乱统计连通块时可能把一块拆成两块。2.4 递归 vs 迭代写 find 时的个人建议find 递归写法简洁但递归深度在路径压缩前可能达到 n 的数量级极端数据下可能爆栈。迭代版本也不难int find(int x) { int r x; while (fa[r] ! r) r fa[r]; // 先找根 while (x ! r) { // 路径压缩 int p fa[x]; fa[x] r; x p; } return r; }第一遍循环找根第二遍循环把沿途节点指向根。两个循环时间加起来 O(n)跟递归一样。我是建议初学先用递归等熟悉后再尝试迭代不要一上来两种写法全写容易晕。这道题数据量用递归完全没问题CF 上很多模板题数据范围大才需要考虑迭代版。3. 完整代码与逐段解析这一版可以直接抄3.1 完整带注释代码直接上最终版我尽量把每一行都写清楚便于你对照理解。#include bits/stdc.h using namespace std; const int MAXN 1005; int fa[MAXN]; // 父节点数组fa[i] 表示 i 的父节点 // 查找 x 所在集合的根节点同时做路径压缩 int find(int x) { if (fa[x] x) return x; // 根节点的父节点是自己 return fa[x] find(fa[x]); // 递归找根顺手把父节点设为根 } // 合并 x 和 y 所在的集合 void unite(int x, int y) { int rx find(x); // 找到 x 的根 int ry find(y); // 找到 y 的根 if (rx ry) return; // 本来就在同一个集合什么都不用做 fa[rx] ry; // 否则把 rx 的根挂到 ry 的根下 } int main() { ios::sync_with_stdio(false); // 关闭 C 和 C 输入输出的同步加快 cin cin.tie(0); // 取消 cin 和 cout 的绑定 int n, m; while (cin n n ! 0) { // 多组数据n0 时退出 cin m; // 初始化每个村庄独立成集自己的父节点是自己 for (int i 1; i n; i) fa[i] i; // 读入已有的 m 条道路并合并集合 for (int i 0; i m; i) { int a, b; cin a b; unite(a, b); // 道路相当于把 a、b 连在一起 } // 统计连通块数量根节点个数 int cnt 0; for (int i 1; i n; i) { if (find(i) i) cnt; } // 需要修的路数 连通块数 - 1 cout cnt - 1 \n; } return 0; }3.2 重点代码细节说明初始化循环从 1 开始到 n因为题目村庄编号是 1~n不要开成 0~n-1。如果你习惯 0 基那全代码都要相应改但没必要和题目较劲。find 和 unite 都是全局函数直接操作 fa 数组。注意 unite 中 rx ry 时直接 return这个判断可以省掉一次无意义挂接更重要的是避免形成环。虽然树结构没有环概念但重复合并同一个集合本身没意义也影响秩的维护养成这个习惯对以后做复杂题有好处。统计连通块数时我写的是 find(i) i这比单独写if (fa[i] i)更稳。因为某些路径没被压缩过的节点父节点可能不是根但 find(i) 之后 fa[i] 会被更新为根统计结果依然正确。用 fa[i] i 也绝大多数情况下没问题但万一你有某个节点没有调用过 find它的 fa 不会自动更新虽然统计根节点时它如果不是根就一定不是 self-parent所以两种写法结果等价但 find(i) i 更符合逻辑也更保险。3.3 关于输入加速的两行代码代码开头那两行ios::sync_with_stdio(false); cin.tie(0);是卡输入输出时的常用武器。本题 m 最多几千行不加也没事但养成习惯后面对大数据题不至于超时。sync_with_stdio(false)的意思是 cin 不再和 scanf 同步速度能提升几倍cin.tie(0)让 cin 不要每次在输出前刷新 cout避免频繁 flush。不过有一个代价用了sync_with_stdio(false)之后不能再混用 scanf 和 cin 读同一路输入否则缓冲区会乱。这属于细节坑很多新手因此挂过。本题没有混合输入需求所以安全。3.4 通过样例分析代码走位假设输入4 2 1 2 3 4 0初始化后 fa[1]1fa[2]2fa[3]3fa[4]4。读入 1 2unite(1,2)find(1)1find(2)2fa[1]2。读入 3 4unite(3,4)fa[3]4。统计时 find(1) 得到 2路径压缩后 fa[1]2find(2)2 是根find(3) 得到 4find(4)4 是根。cnt2输出 1。也就是再修 1 条路把 {1,2} 和 {3,4} 两组连起来所有村庄就互通了。再看一个稍微隐蔽的情况如果道路已经把所有点连成一个块比如 1-2、2-3、3-4那么 find(1) 递归到 4路径压缩后 fa 全部指向 4cnt1输出 0符合预期。4. 常见问题与调试技巧实录4.1 我踩过的坑和你可能踩的坑第一个坑多组输入判断写错。有人写成while (n ! 0) { cin n; ... }但如果第一次输入就是 0程序不会退出会先读入再判断导致多处理一组空数据。正确做法是像我的代码那样while (cin n n ! 0)先读入读到了而且非 0 才进循环读不到就退出循环。第二个坑忘记初始化 fa 数组。每次数据组开始fa[i] 必须重置为 i。如果上一组的 fa 残留到下一组连通块统计就会错得离谱。我曾经见过有人把初始化放在读 m 之前但少循环了 n导致后面几个村庄没有归位排查半天才发现是for (int i 1; i n; i)写成了 n。第三个坑find 递归写错返回值。比如if (fa[x] x) return x; return find(fa[x]);忘了做路径压缩赋值这种写法修改前功能正确但是速度慢。最怕的是写成return fa[x] x ? x : fa[x] find(fa[x]);少个括号导致编译不过这种小错误多写几次就有肌肉记忆了。第四个坑数据范围不看清。有人看到 n 最大 1000就把 fa 数组开成 105结果 RE。我的建议是开const int MAXN 1005;或者干脆vectorint fa(n1)动态开避免越界。4.2 调试环境搭建与逻辑检查法我没有用什么高级工具就是普通的本地编译加输出关键信息。遇到答案错误时我会在统计连通块前加一行临时输出把所有fa[i]打印出来肉眼扫一遍找规律。如果发现某个根节点不是 self-parent就说明有节点的父指针没有正确更新多半是 unite 里没 find。还有一种情况是答案比真实值小 1那往往是统计时漏掉了孤立点。假设 n3m0没有任何道路三个村各自独立。合并操作没有发生find 后三个全是根cnt3输出 2。修两条路连成一条线例如 1-2、2-3所有村庄连通正确。如果代码统计时用cnt放在if (find(i) ! i) cnt;那就完全反了新手常犯。为了快速验证多组数据输出我习惯把每个样例单独跑观察每组输出是否和手算一致。因为本题输出只有一行一个数字对拍非常容易。4.3 性能实测这种写法到底多快我在本地用 n1000m 随机生成的大约几千条边跑运行时间几乎为零连肉眼可感知的停顿都没有。即使把 n 提高到 10 万并查集加路径压缩也稳稳通过。所以这道题根本不需要担心复杂度真正要担心的是逻辑正确性。但把 n 提高到 100 万时递归 find 会爆栈风险增加这时建议改成迭代版本。不过洛谷时限宽松通常递归也能过。我一般建议凡是 n 超过 10 万的题果断用迭代 find不赌编译器优化。4.4 题后复盘这题为什么适合入门很多新手刷这题直接套板子但不知道板子为什么是板子。我觉得这题最大的价值在于它让你理解“连通块”“集合关系”“根节点”这几个抽象概念而且答案公式非常简单直观。一旦你在这题里把并查集的建模逻辑吃透后面做“食物链”“银河英雄传说”这种进阶题时你会少很多痛苦。复盘时我会问自己三个问题为什么答案是 cnt-1为什么能用并查集表示连通性路径压缩到底优化了什么能把这三个问题用白话说清楚说明真的懂了。5. 题外拓展并查集的延伸与变式思考5.1 如果题目变成“至少需要修哪些路”这题只问数量不要求具体方案。如果改成输出具体路径就需要额外记录每条合并操作连的是哪两个根节点。思路也很直接在 unite 里当 rx ! ry 时把这条边即 rx 和 ry 之间输出这就是一条可行的“新修道路”。因为每合并一次连通块数减 1最终 cnt-1 条边刚好把所有块连起来。这种“输出方案”的变式在竞赛中偶尔出现。我建议你思考时抓住本质答案数量是 cnt-1方案就是构造 cnt-1 条连接不同根的边。可以把第 i 个根和第 i1 个根连起来也可以随便枚举。5.2 带权并查集和种类并查集村村通是纯并查集最简单的形态。下一阶段可以玩带权并查集比如“食物链”要求维护节点到根的距离取模关系再比如“银河英雄传说”要维护集合大小和节点到根距离。这些题目的核心还是在 find 递归时更新附加信息unite 时处理根的合并逻辑。把普通 find 和 unite 练到肌肉记忆之后再叠加额外数组就会顺畅很多。我个人经验是先从“统计连通块”这种纯结构题入手把模板背熟再去接触带权版本。不要在第一天就挑战高难度否则很容易被打击到。5.3 反向建边思想Kruskal 算法前奏村村通并查集本质是 Kruskal 最小生成树算法的前置组件。Kruskal 的做法是把边按权值排序从小到大枚举如果边的两个端点在不同集合就合并同时累加权值。这个过程依赖于并查集的 find 和 unite跟村村通完全同源。如果你未来准备打蓝桥杯或 CSP建议把这个题作为起点再接一道最小生成树模板题例如“最短网络”之类的。两题对比着做你会发现并查集在路径规划和连通性问题里有多常用。到那时你回头看这道村村通会有一种“原来那么简单”的感慨。5.4 对代码风格的自我要求最后闲聊两句代码风格。我在写并查集时会强制自己把 find 和 unite 抽成独立函数绝不在 main 里直接修改 fa 数组做合并。这样代码可读性高调试时也能直接在函数里加输出。命名上统一用 fa、find、unite不要一会儿用 father一会儿用 search给自己添堵。另外我习惯在代码开头先把输入用cin n m读全再进循环避免边读边合并导致思路混乱。这种小习惯积累多了写复杂题时不容易出低级错误。我个人在实际操作中的体会是并查集是我用过的数据结构里最接近“思维直觉”的一种只要你记得“找根、挂根”这四字口诀几乎所有问题都能迎刃而解。洛谷 P1536 这道题代码量不大却把并查集的核心应用场景演绎得很完整非常适合作为入坑第一题。最后再分享一个小技巧做完这道题你可以尝试用三种不同的 find 写法递归路径压缩、迭代路径压缩、不压缩分别提交观察运行时间差异。这种对比实验比自己空想“路径压缩为什么好”要直观得多。等你真实看到压缩版瞬间跑完、不压缩版卡着时限过你对这个优化的理解会彻底扎进脑子里。
阅读完成 · 觉得有帮助？
