畅通工程与并查集：从连通分量到最少补边数

1. 先拆标题ZJUKY110 和“畅通工程”分别透露了哪些信息1.1 题目编号背后的语境第一次看到“ZJUKY110 畅通工程”这个标题如果不熟悉题库命名规则很容易一头雾水。拆开看“ZJUKY110”更像是某个教学平台或学校内部题库里的唯一编码其中“ZJU”通常代表题目来源的标识“KY110”可能是课程编号或者题目序号。真正给做题者提供方向的是后半部分“畅通工程”。很多数据结构课程会把这一题放在图论章节的第一课目的是让学生在正式学习邻接表、割点、最短路径之前先用一个轻量级问题掌握“连通性”的概念。“畅通工程”这个题目名在编程题库里出现频率极高从最早的基本连通题到后续演变出的各类带成本、带坐标的版本整个系列一直在考并查集和最小生成树。对刚接触数据结构的人来说这几乎是绕不开的第一道图论作业题。1.2 输入输出约定的完整描述把标准输入输出格式完整展开是这样的。输入包含多组测试数据每组第一行包含两个整数 N 和 MN 代表城镇数量M 代表已经规划的道路数量。城镇编号从 1 到 N。当输入的 N 等于 0 时表示所有测试数据结束程序不需要处理这一组。之后的 M 行每行两个整数 a 和 b含义是城镇 a 和 b 之间已经存在一条可以通行的道路。对每条道路来说a 和 b 之间不一定满足 a b也没有保证同一对城镇只会出现一次所以代码要能容忍重边和乱序边。输出要求是一行一个整数表示要让整个区域畅通最少还需要新建的道路数量。比如输入三组测试数据输出就对应三行数字。1.3 这个题真正在考什么表面上看这题考的是有没有读懂题干实际上考的是三件事。第一能否把文字描述转化为无向图模型城镇是顶点道路是边。第二能否准确统计连通分量数量。第三能否证明“补边数 连通分量数 - 1”这个结论。很多复习代码的人会忽略第三点把公式死记硬背下来这样做基础题还行一旦遇到需要推导的变种题立刻卡住。所以第 2 节我会专门把推导过程拆细这部分直接决定你能不能把同一套路迁移到其他题上。2. 设计思路为什么答案是“连通分量数 - 1”2.1 从文字到图模型的转化过程在无向图 G(V, E) 里V 是城镇集合E 是道路集合。两个城镇如果直接相连它们之间就有一条边如果一个城镇能通过若干条边到达另一个城镇我们就说它们属于同一个连通分量。连通分量是极大连通子图分量内部的任意两个点都可以互相到达而不同分量之间没有任何边。题目要求是让整个图只有一个连通分量。在这个前提下新增一条连接两个不同分量的边会立即把两个分量合并成一个新增一条连接同一分量内部的边不会改变分量数量。问题于是等价于通过最少的边数把多个连通分量合并成一个。2.2 为什么最少补边数恰好是 k - 1记当前连通分量数量为 k。先看下界一次合并操作最多只能让分量数减一不可能一次减少两个或更多分量。要把 k 最终变成 1至少需要 k - 1 次操作所以答案不可能小于 k - 1。再看上界构造一种方案随意挑第一个连通分量的任意点 x再挑第二个连通分量的任意点 y连接 x 和 y这两块立刻合并成一块。接着用合并后的新块里的任意点去连第三个分量的任意点如此继续。每次操作都能让分量数量恰好减一因此 k - 1 次操作足够。下界和上界相等答案恰为 k - 1。这个证明过程很朴素却非常重要很多变种题都依赖类似的构造思路。比如最小生成树里加一条边减少一个连通分量的思想一直在被复用。2.3 备选方案对比DFS/BFS 和并查集如果考试时间紧用 DFS/BFS 直接统计连通分量也能做对。思路是建立邻接表用一个 visited 数组标记访问情况外层循环遍历所有点没访问过就从该点开始做一次 DFS 或 BFS并把访问到的点全部标记每启动一次搜索就是一个新的连通分量。实现难度不高时间复杂度 O(NM)同样可以接受。但并查集的优势在于它不需要预先构建邻接表。输入边的时候我们一边读一边合并后面的查询和统计都变得极其自然。更重要的是这种方式能处理在线场景如果后续还有新增边不需要重新遍历图只需再调用一次 union 就更新了。2.4 动态连通性在工程里的意义实际系统里一张静态图的情况反而不多更多时候是不断有节点加入、有边新增。比如服务注册中心新增实例、容器集群的节点互联、缓存系统新增副本之间的通信链路。每次改动都全图扫描一遍代价很高而并查集天然支持增量维护所以它不只是课程作业里的技巧也经常出现在系统设计思路中。3. 并查集一道题的灵魂数据结构3.1 从数组出发理解“集合”并查集的原始数据就是一个数组 parent下标是点的编号值是该点的父节点。开始时每个点孤立所以 parent[x] x。三个基本操作都围绕这个数组展开初始化给每个点设成自己的根查找 find(x) 顺着父指针一路向上走到根合并 unionSets(a, b) 把 a 所在集合和 b 所在集合合并。一句话概括parent 数组表示的是一棵多叉树根节点是集合代表元。找根的过程就是沿着 parent 上跳的过程。也可以用“直系领导”来类比每个员工记录自己的直系领导领导再向上有领导直到最大的领导指向自己。查询“你和另一个人是否属于同一部门”就是分别追溯两个人的最大领导看是不是同一个人。部门合并时不需要通知每一个员工只要让两个部门的最高领导之间建立上下级关系整个部门在逻辑上就合成一个集体了。3.2 路径压缩让树变矮的关键优化在没优化的并查集里如果合并操作总是把一棵树的根挂到另一棵树的某个子节点上树会越来越像单链表find 的复杂度会退化到 O(N)。路径压缩的思想是在 find(x) 的过程中顺路经过的所有节点的父指针都直接指向根。下一次再查这些节点时一步就能到达根查找代价几乎变成 O(1)。递归实现路径压缩的代码很经典int findRoot(vectorint parent, int x) { if (parent[x] ! x) { parent[x] findRoot(parent, parent[x]); } return parent[x]; }这个写法在递归回溯时把当前节点的父指针改成了根。如果担心递归太深可以改成迭代版第一遍循环找根第二遍循环把路径上的节点全部直连根int findRoot(vectorint parent, 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; }3.3 按秩合并让树长得更均衡路径压缩只在查询时发生合并时如果完全不管树的形状仍然可能构造出很不平衡的树。按秩合并的思想是记录每棵树的秩秩近似等于树的深度合并时让秩较小的树挂到秩较大的树下面。这样整棵树的深度增长得更慢后续查找更省事。实现时用一个 rank 数组。刚开始所有点的秩都是 0合并时先比较两个根节点的秩把秩小的根的父亲设为秩大的根如果两者秩相等选一个做根并把它的秩加一。加了按秩合并后单独操作的复杂度都保持在 O(log N)和路径压缩配合后还能进一步降到 O(α(N))。3.4 复杂度分析为什么能当作常数对于数据范围比较大的题目人们常说并查集单次操作均摊时间复杂度是 O(α(N))。这里的 α 是逆阿克曼函数。不用去背函数定义只需要知道它在现实中增长极慢即使 N 大到难以想象α(N) 也不超过 5。所以实际编码中完全可以把它当作常数处理。也正是因为这一点并查集能在很多高数据量场景里变成最优首选。4. 完整的实战编码过程4.1 环境准备与输入加速写这道题前先把编译器打开。C 版本建议 C11 或以上因为代码里会用到 vector容器初始化更方便。另一个建议是关闭 C 和 C 输入输出的同步ios::sync_with_stdio(false); cin.tie(nullptr);这两行不计入算法复杂度但对多组输入有明显的提速效果。与默认状态的 cin 相比关闭同步后能快不少。被大数据卡住超时的时候有时不是算法问题而是输入输出层面的开销。4.2 逐模块拆解初始化、读边和统计一开始初始化int n, m; while (cin n m n ! 0) { vectorint parent(n 1); vectorint rank(n 1, 0); for (int i 1; i n; i) { parent[i] i; } ... }这里每组测试数据都重新构造 parent 和 rank保证上一组数据不会污染下一组。数组大小开成 n 1是为了让下标从 1 开始下标 0 的槽位空出来不用。然后逐条读道路并合并for (int i 0; i m; i) { int a, b; cin a b; unionSets(parent, rank, a, b); }读入的顺序不影响并查集结果因为合并操作满足交换律和结合律。重边也没关系union 时会先判断两个根是否相同相同就直接返回。统计连通分量int components 0; for (int i 1; i n; i) { if (findRoot(parent, i) i) { components; } } cout components - 1 \n;每个根节点都是集合代表元根的特征就是 parent[i] i。统计根的个数就是连通分量的个数。4.3 手把手过一遍小型用例假设输入是4 2 1 2 3 4 0 0初始化后 parent 为 [0, 1, 2, 3, 4]四个点各自独立。读入第一条边 1 2find(1)1find(2)2根不同执行合并。rank 都为 0所以把 2 的父节点设为 1rank[1] 变成 1。此时 parent 变成 [0, 1, 1, 3, 4]。读入第二条边 3 4find(3)3find(4)4两个根不同执行合并。把 4 挂到 3 下面rank[3] 变成 1。此时 parent 变成 [0, 1, 1, 3, 3]。统计时从 1 到 4 依次判断1 是根2 的根是 1 但本身不是根3 是根4 的根是 3 但本身不是根。所以连通分量数是 2答案 2 - 1 1。结果与预期完全一致。4.4 完整代码C#include iostream #include vector using namespace std; int findRoot(vectorint parent, int x) { if (parent[x] ! x) { parent[x] findRoot(parent, parent[x]); // 路径压缩 } return parent[x]; } void unionSets(vectorint parent, vectorint rank, int a, int b) { int ra findRoot(parent, a); int rb findRoot(parent, b); if (ra rb) return; if (rank[ra] rank[rb]) { swap(ra, rb); } parent[rb] ra; if (rank[ra] rank[rb]) { rank[ra]; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m n ! 0) { vectorint parent(n 1); vectorint rank(n 1, 0); for (int i 1; i n; i) { parent[i] i; } for (int i 0; i m; i) { int a, b; cin a b; unionSets(parent, rank, a, b); } int components 0; for (int i 1; i n; i) { if (findRoot(parent, i) i) { components; } } cout components - 1 \n; } return 0; }如果你更喜欢用静态数组可以直接声明int parent[100005];但要注意不同题目 N 的上限可能不同数组大小必须开够。用 vector 一是省空间二是不容易越界。4.5 有关变量命名的经验变量命名里我习惯把 rank 写成 rankfindRoot 而不是 findunionSets 而不是 union。因为 union 在很多 C 环境里和内置关键字或同名函数冲突直接用会带来不必要的编译错误。find 也和标准库函数有重叠建议加后缀。这些细节能帮初学者少踩莫名其妙的坑。5. 测试、对拍与边界用例5.1 为什么样例不能代表一切题库给出的样例通常很简单目的是演示功能不是验证正确性。比如题目示例可能只有两个城镇一条路答案 0或者三个城镇两条路答案 1。通过了样例不代表代码能处理所有边界情况。我每写一次图论题都会顺手多构造几组数据。单个测试用例最好覆盖这些情况没有任何道路的纯孤立点集合只有一个城镇和零条道路一条道路的端点都是同一个城镇多条重复边所有点在一条直线上串成链所有点全部连通。每组输出都要能手工推演一遍。5.2 边界用例推演下面这组用例建议直接放进本地测试文件1 0 3 3 1 2 2 3 1 3 5 0 4 2 1 2 3 4 0 0第一组 N1M0只有一个城镇不需要任何道路答案是 0。第二组三个城镇三条边已经全连通答案是 0。第三组五个孤立城镇答案是 4。第四组两两成对两个连通分量答案是 1。最后一组 0 0 代表输入结束。5.3 自环和重边的处理如果道路给了“1 2”和“2 1”两条并查集合并结果和只有一条“1 2”完全相同因为合并操作会先判断两个端点是否同根同根就跳过。自环“1 1”更是什么都不触发。这些都是无害输入但如果代码在合并前没有判断或者用邻接矩阵存图就可能出现重复边引起的问题。并查集天然免疫重边这是它在这类题目里特别省心的原因。5.4 用暴力算法互相验证想进一步确认代码正确可以写一段用 DFS 统计连通分量的暴力版本然后在 N 比较小比如 N 不超过 10 的范围内生成随机图把两份代码的输出逐组对比。随机图生成规则很简单从 1 到 N 随机生成若干条边允许重复允许自环。跑上几千组数据如果两边结果一致基本可以放心提交。这个流程叫对拍是搞算法题的人都会用到的测试手段拿来验证作业题同样有效。6. 常见问题排查与避坑清单6.1 编译和初始化类问题第一类问题多出在 C 的细节上。数组开成 n 而不是 n1使用编号 n 时越界多个测试用例之间parent 数组或 rank 数组没有重新初始化不同测试用例里残留上一次的全局数据。这些都是很常见的错误最好用 vector 在每组数据内重新构造从根本上避免跨组污染。6.2 逻辑层面的隐蔽错误第二类问题更隐蔽。合并时直接判断 parent[a] ! parent[b] 就执行合并没有先 find这样实际上只更新了某个节点的父指针没有把整个集合合并导致统计结果多出一两个分量。本质上是因为对“集合代表元”这个概念没吃透。还有一种隐蔽错误统计连通分量时用了 findRoot(i) i但有些写法把 findRoot 写成了不压缩路径的版本在数据多、结构复杂时可能出现查到的根不是真正根的情况。解决方法是先执行压缩版 find再判断根节点身份。6.3 性能与内存的隐忧虽然并查集快但代码写不好也会退化。比如用 vector 存储 parent 但不做路径压缩在一条长链上反复 find每次都要走到链尾最坏复杂度会退化到 O(NM)。一些 N 到 10^5、M 到 10^5 的用例会直接超时。应对方法就是两个优化都做上合并时按秩查找时压缩。内存方面如果 N 最大是 10^6parent 数组用 int 大约 4MBrank 数组又是 4MB静态开完全没问题。如果 N 更大可以考虑用 short 存 rank但没必要为了这个小题优化到那种程度。6.4 提交时的输出格式和细节这道题的输出要求每行一个整数。有人写成cout components - 1 endl;也能过但每次 flush 缓冲区会慢一些。刷大数据时建议用\n而不是 endl。另外千万别输出任何提示文字比如“答案是”否则评测系统会判错。多组输入如果格式要求有空行题目会明确说明这题没有所以每行输出完直接换行即可。现象可能原因解决方式输出比正确答案大 1下标从 1 开始但初始化循环从 0 开始或统计时把 0 号点也算进去初始化只做 1 到 n统计也只做 1 到 n输出比正确答案小 1合并时没有找到根把非根节点直接挂到另一个节点下面使用 findRoot 得到根后再合并M0 时答案不对没有处理 M0 的输入或者循环条件写错即使 M0也要正常初始化并统计分量超时缺少路径压缩或按秩合并两个优化都加上输入用快速 IO递归深度爆栈find 写成无压缩递归且数据成链使用迭代 find 或在递归中做路径压缩评测结果 PE / WA输出多空格、多换行严格按格式输出只输出一个整数加换行7. 大胆联想同一题型的 N 种变形7.1 判断是否已全连通应用场景里常见的是判断图是否已经全连通。只需要把最后输出改成 components 是否等于 1 的判断结果其余代码几乎不变。这类变体常出现在面试里因为面试官想快速确认你理解连通分量的意义。7.2 最小生成树Kruskal如果把道路分成“已建”和“可建”两类且可建道路有成本题目立刻升级为最小生成树问题典型的是“还是畅通工程”这类变体。Kruskal 做法是把所有可建道路按成本升序排序用并查集逐个连接只要不会成环就加入选择 N-1 条边后停止累加成本输出。并查集在 Kruskal 里的作用是高效的环路检测。因为如果两个端点已经在同一分量里再加这条边一定会形成环干脆跳过。复杂度 O(M log M)瓶颈在排序不在并查集。7.3 带权并查集如果边上有数值信息并且需要动态维护比如两个城镇之间的延迟值、两个用户之间的关系分值那就需要在父节点关系上额外保存“到父节点”的权值。find 时累加权值union 时根据已知两个节点的相对值推算出新的权值关系。常见经典题有食物链、奇偶游戏等适合在掌握基础版本之后继续钻研。7.4 冗余连接问题有些题目反过来问在一棵已经多加了边的树上找到那条导致环出现的冗余边。并查集扫描边列表当发现一条边的两个端点已经在同一集合中时这条边就是冗余边。这个思路在动态维护环境的异常检测里很有用可以快速定位造成循环引用的连接。8. 对这道题的一些个人体会做这类基础算法题我最大的感受是不要把结论当成理所当然。刚学并查集时我也曾直接把“components - 1”背下来直到有一天被问为什么不是 components才认真去想。一旦认真想了后面学最小生成树、带权并查集、甚至处理环检测问题都会顺水推舟。建议在读这篇文章后抽出十分钟把代码重写一遍不要复制粘贴。写的过程中体会三件事find 的路径压缩到底改了什么union 按秩合并为什么能保性能主循环统计根节点时为什么不会漏点。如果这三件事都能自己解释清楚这道“ZJUKY110 畅通工程”就算真正内化了。之后再去挑战那个系列的后续题目你会发现自己已经比别人省了一整个踩坑过程。