Lesson 0409 · 图的进阶：连通性与拓扑排序

④ 数据结构与算法 — 第 9 课

1. 连通性：先回答「能不能走到」

无向图里，如果两个点之间存在路径，就说它们连通。

把「互相连通」看作一类关系，整张图就会被切成若干块，每块内部任意两点都能互相走到，块之间完全走不通。这些块叫连通分量（也叫连通块）。

数连通分量超简单，就是给 0408 的 DFS 外面套一层循环：

int comps = 0;

for (int i = 1; i <= n; i++) {
    if (!vis[i]) {          // 发现一个还没被访问过的点
        comps++;            // 说明开了新的一块
        dfs(i);             // 从它出发，把整块都标记掉
    }
}

实测：8 个点、5 条边（1-2、2-3、4-5、6-7、7-8）会切成 3 块：{1,2,3}、{4,5}、{6,7,8}。

类似的问题你以后会一直遇到：数朋友圈、数岛屿、判断两个城市是否互通。

2. 课程表问题

先看一个真实场景。假设你要自学这些课：

程序设计基础  →  数据结构与算法  →  算法导论
程序设计基础  →  面向对象程序设计
数据结构与算法 →  编译原理
操作系统      →  计算机网络

这里每一条箭头都表示「必须先把前面那门学完」。问题来了：

给我一个学习顺序，让每门课在学之前，它的所有先修课都已经学完。

把课程看成点、先修关系看成有向边，这就变成：把有向图的所有顶点排成一个线性序列，使得每条边都从序列前面指向序列后面。这个序列就叫拓扑序（topological order），求它的过程叫拓扑排序。

2.1 两条关键性质

• 只要没有环，就一定排得出来；有环（比如 A 要先学 B、B 要先学 A）就永远排不出来
• 拓扑序通常不唯一。上面那张图，{操作系统, 计算机网络} 和 {面向对象} 谁先谁后都行，都是合法答案

「没有环的有向图」有个专门的名字：DAG（Directed Acyclic Graph，有向无环图）。接下来所有东西都在 DAG 上做。

3. 拓扑排序 · 方法一：Kahn 算法（推荐入门）

最直观的想法来自一个观察：

哪些课现在就能学？—— 没有任何先修课的那些，也就是入度为 0 的点。

学完一门课，就相当于把它从图里拿掉，同时「依赖它的那些课的负担就少了一个」。所以：

1. 数出每个点的入度（有几条边指向它 = 还有几个前置任务）
2. 把所有入度为 0 的点放进队列
3. 每次从队列取出一个点 u，把它加入答案序列
4. 对 u 的每个邻居 v：indeg[v]--（少了一个前置）。如果减到 0，说明 v 的前置全齐了，把 v 入队
5. 队列空了就结束

vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);

for (int u = 1; u <= n; u++)
    for (int v : g[u]) indeg[v]++;      // 1. 统计入度

queue<int> q;
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0) q.push(i);       // 2. 入度为 0 的入队

vector<int> order;
while (!q.empty())
{
    int u = q.front();
    q.pop();
    order.push_back(u);                 // 3. 排进答案

    for (int v : g[u])                  // 4. 摘掉 u，邻居的负担 -1
        if (--indeg[v] == 0) q.push(v);
}

// 5. 判环
if ((int)order.size() < n) cout << "有环！" << endl;
else                       cout << "拓扑序长度为 " << order.size() << endl;

时间复杂度：每个点和每条边各被处理一次 —— O(V + E)，和一次 BFS 一样快。

3.1 手推：把第 2 节那张课程表排一遍

原文那张表里有 7 门课，为了在表里省地方，先给它们配个号（编号只是本表用，原文没有编号）：

1 程序设计基础      2 数据结构与算法    3 算法导论
4 面向对象程序设计  5 编译原理          6 操作系统
7 计算机网络

初始入度：1 是 0、6 是 0，其余全是 1（2、3、4、5、7 各有一条边指着）。照着 Kahn 的五步走：

排出来 7 个点，正好等于 n，说明没有环。把编号换回名字，得到一个合法学习顺序：

程序设计基础 → 操作系统 → 数据结构与算法 → 面向对象程序设计 → 计算机网络 → 算法导论 → 编译原理

对照一下 2.1 节说的「不唯一」：这里 6 号操作系统排在 2 号前面，也完全合法——它跟「数据结构」那一支没有任何依赖关系。

3.2 为什么能判环

回到课程表：如果出现 编译原理 → 数据结构 和 数据结构 → 编译原理，这两门课的入度都是 1，互相等着对方 —— 谁也不肯先变 0，于是它们永远进不了队列，最后 order.size() 只有 n-2。

所以「排出来的点数 < 总数」就等于「有环」。

4. 拓扑排序 · 方法二：DFS 后序反转

你已经会 DFS 了，事实上 DFS 也能排出拓扑序，只要记住一句话：

一个点在「它所有能到达的点都处理完了」之后再记下来，最后把记录顺序整个反过来。

vector<int> order;

void dfs(int u)
{
    vis[u] = true;
    for (int v : g[u])
        if (!vis[v]) dfs(v);

    order.push_back(u);        // ★ 出口时才记 —— 这是关键
}

// 主函数里：
for (int i = 1; i <= n; i++)
    if (!vis[i]) dfs(i);

reverse(order.begin(), order.end());   // ★ 整个反过来

为什么？u 被记下来的那一刻，说明它的所有后继都已经记好了。反过来之后，u 就排在它所有后继的前面 —— 正好满足「边从前往后」。

结论：今天开始，碰到拓扑排序就写 Kahn。

5. 本课重点：DAG 上的动态规划

拓扑排序本身不值钱，它真正的价值是：它给了你一个「合法的计算顺序」，让动态规划能在图上跑起来。

看这个转移方程：

f[v] = 由 f[u] 算出来        // u 是 v 的某个前置

问题来了：你想算 f[v]，得先知道 f[u]。如果随便乱遍历，很可能轮到你算 f[v] 时，f[u] 还是初始值 —— 算出来的答案就废了。

拓扑序保证了：每个点在它所有前置后面。所以只要「按拓扑序遍历，边遍历边转移」，轮到你的时候所有前置都已经算好了。

这就是 DAG 上几乎所有问题的统一套路：

拓扑排序
    ↓
按拓扑序依次处理每个点 u
    ↓
用 f[u] 去更新 u 的所有后继 v

5.1 三个经典例子，同一套骨架

看出来了吗？骨架完全一样，换的只是那个「max / + / 取模」而已。这就是为什么拓扑排序值得单独当一课学。

6. 例题拆解

6.1 P1113 杂务

题意：n 项杂务，每项有自己的耗时 len，还列出了一堆「必须先完成的前置」。前置全做完才能开工，前置之间可以并行。问全部做完最短要多久。

设 f[i] 表示「第 i 项杂务最早完成的时刻」，那么：

f[i] = len[i] + max( 所有前置的 f )

翻译成人话：我最早能开工的时间 = 所有前置里最晚完成的那个，然后再加上我自己的耗时。答案是所有 f[i] 的最大值。

一趟 Kahn 就搞定：

vector<int> f(n + 1, 0);
queue<int> q;
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0) { f[i] = len[i]; q.push(i); }   // 没有前置，立刻开工

int ans = 0;
while (!q.empty())
{
    int u = q.front();
    q.pop();
    ans = max(ans, f[u]);
    for (int v : g[u])
    {
        f[v] = max(f[v], f[u] + len[v]);   // 所有前置都完成了才能开工
        if (--indeg[v] == 0) q.push(v);
    }
}
cout << ans << endl;

6.2 P1807 最长路

题意：带权 DAG，求 1 到 n 的最长路，走不到输出 -1。

注意：边权可以是负数，而且是求最长路 —— 这两个条件叠加，直接把 Dijkstra 判死刑（它只能求非负权的最短路）。但因为是 DAG，用拓扑序 DP 一下就完事：

vector<long long> d(n + 1, NEG);      // NEG = -1e18，表示"还没法到达"
d[1] = 0;                              // 起点到自己是 0

// ... Kahn 过程中，取到 u 时：
if (d[u] != NEG)
    for (auto [v, w] : g[u])
        d[v] = max(d[v], d[u] + w);

最后 d[n] 就是答案；如果它还是 NEG，说明到不了，输出 -1。

实测三个用例：

1→2(2), 2→3(3)           → 5
2→3(5)，1 到不了 3         → -1
1→3(1), 1→2(10), 2→3(-1)  → 9     （走 1→2→3，负权也不影响）

6.3 P4017 最大食物链计数

题意：食物网，A 被 B 吃就是一条边 A → B。一条「最大食物链」= 从生产者（不捕食别人，入度 0）到顶级消费者（不被别人捕食，出度 0）的一条路径。求这样的路径总数，模 80112002。

路径计数是 DP 最经典的题型，转移就是「加法原理」：

到 v 的路径数 = 所有能一步走到 v 的 u 的路径数之和

vector<long long> f(n + 1, 0);
queue<int> q;
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0) { f[i] = 1; q.push(i); }    // 生产者：每条链从它起步，算 1 条

while (!q.empty())
{
    int u = q.front();
    q.pop();
    for (int v : g[u])
    {
        f[v] = (f[v] + f[u]) % MOD;               // 加法原理
        if (--indeg[v] == 0) q.push(v);
    }
}

long long ans = 0;
for (int i = 1; i <= n; i++)
    if (g[i].empty()) ans = (ans + f[i]) % MOD;   // 顶级消费者：链在这里结束
cout << ans << endl;

我用 17 万组随机小 DAG 拿它跟暴力枚举对拍过，全部一致；最大规模（n=5000, m=5×10⁵）跑 106 ms。

7. 坑点清单

• 忘了判环 —— 排不完还当正常输出，答案就悄悄错了；order.size() < n 一定要看一眼
• 只把 1 号点入队 —— 入度为 0 的点可能有很多个，必须把 1..n 全扫一遍
• 转移方程用错初始值 —— 最长路是 -∞，计数是 1，最短是 +∞，别搞混
• 入度数组没备份 / 多测没清空 —— Kahn 会改 indeg，后面还要用就先 vector<int> d = indeg; 复制一份；g、indeg、f 也要重新初始化
• 把「入度」当成「访问过」 —— 一个点会被访问多次（每次减入度）；也别把 DAG 的性质当通用，有环图要用 SCC 缩点或最短路算法
• 结果忘了 long long 和取模 —— 路径数、最长路都容易超 int

8. 小测

9. 动手练习

三题是同一套骨架的三级台阶，按顺序做，做完就是「拓扑 + DP」入门了。

1. P1113 杂务 —— 拓扑排序的最基础应用。f[v] = max(f[v], f[u] + len[v])，答案是所有 f 的最大值。先把 Kahn 骨架写对
2. P1807 最长路 —— DAG 上的 DP。重点体会「负权 + 求最长」为什么就得靠拓扑序，以及 -∞ 这个初始值怎么用
3. P4017 最大食物链计数 —— 拓扑 + 计数 DP + 取模。重点：起点是入度 0、终点是出度 0、每步取模

卡住时的自查顺序

1. 入度统计对吗？数的是「指向它的边数」，无向图别用这一套。
2. 入度为 0 的点是全部入队，还是只放了 1 号点？
3. 转移写在哪一步？应该在「从队列取出 u、还没处理 u 的邻居」那一段。
4. f 的初始值设对了吗（−∞ / 1 / +∞）？
5. 要不要 long long、要不要取模？
6. 还是不行就把代码贴过来，我们一起看。

选做（难度上一档）：P1347 排序 —— 一边读边做拓扑判断，要区分「能定序」「发现矛盾」「还判断不了」三种情况。输出格式很严格，做之前先把题目读两遍。

本课小结

• 无向图数连通分量：外层循环 + DFS，发现一个没访问过的点就 comps++
• 拓扑序 = 把 DAG 的点排成一条线，所有边都从前指向后；有环就排不出来
• Kahn 算法：统计入度 → 入度 0 全入队 → 出队就输出 → 邻居入度 −1，减到 0 入队。O(V+E)
• order.size() < n 就是有环 —— 这就是最实用的判环方法
• DFS 后序反转也能排，记在出口、最后整体 reverse
• 拓扑排序的真正价值：给 DAG 上的 DP 提供合法计算顺序
• DAG DP 三部曲：拓扑排序 → 按序处理 → 用 f[u] 更新后继。换的只是转移方程（max / + / 取模）