第4章 疆域勘定：连通性、环与并查集

第 4 章 · 疆域勘定：连通性、环与并查集

章节摘要：远征队已经会走会看，接下来要回答地图上的政治问题：这片疆土分成了几块势力范围？哪些区块内部双向皆可通行？哪些道路围成了回路？本章把"连通"从一个日常词升级为一整套可计算的判定技术——无向图用连通分量清点势力范围，有向图用强连通分量刻画"你来我往"的作战区块，回路排查则交给并查集这件轻巧兵器。全章的方法底座正是上一章练成的两种遍历步法：深度优先的时间戳在这里第一次真正上岗。

本章知识点清单

读完本章，下列知识点应当能经得起考核：

1. 给出连通与连通分量的形式化定义，并用遍历实现分量清点与分量标记。
2. 说明"弱连通、单侧连通、强连通"三级判定之间的包含关系与反例。
3. 手写 Kosaraju 算法的两次深度优先，并解释"反图上按完成时间递减访问"为何奏效。
4. 区分树边、回边、前向边、横边，用"灰到灰"的回边判定有向环。
5. 实现并查集的查找与合并，解释路径压缩与按秩合并各自的摊还代价。
6. 用并查集完成无向图环检测与连通分量合并的完整代码演练。

核心概念速览

金句：所谓连通，不是"看起来连在一起"，而是"存在一条可走通的路径"——前者靠眼睛，后者靠算法。

子章节导航

第 1 节"连通分量：清点势力范围"从测绘场景切入，给出分量标记的完整实现，并把"两点是否同属一个分量"变成一次查询。它同时是无向图与有向图、后续所有"分而治之"策略的第一步。

第 2 节"强连通分量：双向通行的作战区块"进入有向地形，讲清 Kosaraju 两遍深度优先的妙处，并展示"缩点成有向无环图"这一贯穿全册的操作——调度、编译、网络分析里它反复出现。

第 3 节"环检测与并查集：排查地图上的回路"先解决有向图（回边判环），再引出并查集这件专门对付无向连通性的兵器，路径压缩与按秩合并的摊还分析在这里给出直觉版论证。

子章节之间的逻辑关系

一句话论点：分量回答"分几块"，强连通回答"哪块能互达"，环检测回答"哪条路会绕回来"——三者共用深度优先的地基，又各自长出新的兵器。

   遍历步法(第3章)
        │
   ┌────┼─────────┐
   ▼    ▼         ▼
 连通分量  强连通分量   环检测
 无向·标记  有向·Kosaraju  有向·回边 / 无向·并查集
   │        │缩点          │
   │        ▼              │
   │      DAG ──────────→ 第6章 拓扑排序
   └── 分块治之 → 第9/10章 网络分析的地基
​

前置知识与后续延伸

前置：第 3 章的深度优先实现与"发现、完成"双时间戳、队列与栈的基本用法。并查集一节不依赖前面任何高级内容，可独立阅读，但它的动机来自环检测场景。

后续延伸：强连通分量的缩点结果是有向无环图，是第 6 章拓扑排序的直通票；并查集在第 6 章 Kruskal 算法中担任"成环检测器"的核心角色；连通分量作为图的粗粒度摘要，是第 10 章社区发现的第一块踏脚石。可以说本章是承上启下的枢纽——遍历步法在这里兑换成第一批结构判定能力。