拓扑排序

前言

大学选课有先修要求：学”数据结构”之前必须先学”编程基础”，学”算法”之前必须先学”数据结构”，学”编译原理”之前必须先学”算法”。怎么排一个合法的选课顺序？

把每门课看成一个节点，先修关系看成有向边（$A \to B$ 表示 $A$ 必须在 $B$ 之前），这就是一个有向无环图（DAG）。拓扑排序就是在 DAG 上找一个线性序列，使得对于每条边 $u \to v$，$u$ 排在 $v$ 前面。

拓扑排序不只是”排个序”。它还有一个更重要的身份：DAG 上 DP 的天然计算顺序。最长路、最短路、路径计数、关键路径、任务调度——只要问题能建模成 DAG 上的 DP，第一步就是拓扑排序。为什么？因为拓扑序保证了：当你计算 $dp[v]$ 时，所有 $u \to v$ 的 $dp[u]$ 都已经算好了。不需要记忆化，不需要担心循环依赖。

教材（Tessoku Book）在树的章节（9.5 B65 Road to Promotion Hard）中用了一个类似的思路：从叶子向根计算”阶級”。拓扑排序是这个思路在有向图上的推广。

问题的本质

什么是 DAG？为什么必须有向且无环？

先理解”有向”：边有方向。$A \to B$ 表示 $A$ 在 $B$ 之前，不等于 $B$ 在 $A$ 之前。这和无向图的”连通”不同——有向图中 $A$ 能到 $B$，不代表 $B$ 能到 $A$。

再理解”无环”：如果 $A \to B \to C \to A$，那 $A$ 要在 $B$ 前面，$B$ 要在 $C$ 前面，$C$ 又要在 $A$ 前面——自相矛盾。有环的有向图不存在拓扑排序。

反过来，无环的有向图一定存在拓扑排序。 证明思路：DAG 中一定存在入度为 0 的节点。为什么？反证——如果每个节点都有入边，从任意节点沿入边走，$N+1$ 步后必经过重复节点，形成环，与”无环”矛盾。找到入度为 0 的节点后删掉它，剩下的还是 DAG，归纳即可。

Kahn 算法：“入度为 0 先做”为什么是对的？

入度是有多少条边指向这个节点。入度为 0 意味着没有前置依赖——没有任何节点要求在它之前。

Kahn 算法的流程：

1. 找所有入度为 0 的节点，放入队列
2. 从队列取出一个节点 $u$，加入拓扑序列
3. 删掉 $u$ 的所有出边（$u$ 的每个邻居 $v$ 的入度减 1）
4. 如果 $v$ 的入度变为 0，把 $v$ 加入队列
5. 重复直到队列为空

为什么这样一定能得到合法的拓扑序？ 因为每次放入序列的节点入度为 0——它的所有前置已经处理完了。删掉它的出边后，依赖它的节点少了一个前置。当某个节点的所有前置都处理完（入度归零），它就可以安全地加入序列。

如果最终序列长度 $< N$ 怎么办？ 说明有环——入度为 0 的节点耗尽了，剩下的节点互相依赖，谁也无法先做。所以 Kahn 算法同时给出了环检测：序列长度 $= N$ 则无环，$< N$ 则有环。

DFS 能做拓扑排序吗？——后序的魔法

DFS 也能做拓扑排序，而且代码更短。关键在于后序（post-order）：在 DFS 从节点 $u$ 返回时（而不是进入时）记录 $u$。

为什么后序翻转就是拓扑序？DFS 进入节点时递归处理所有后继。所有后继都处理完（后序记录完毕）后，才记录当前节点。这意味着：如果 $u \to v$，那么 $v$ 一定在 $u$ 之前被记录。翻转后，$u$ 就排在 $v$ 前面——恰好是拓扑序。

DFS 版的优势：代码简洁，不需要维护入度。劣势：检测环需要额外的 onstack 数组（当前递归栈上的节点），比 Kahn 的”序列长度”判断稍复杂。

教材的关联：树上 DFS 和拓扑排序

教材 9.5 B65 Road to Promotion Hard 中，“社员 $x$ 的阶級 = max(部下的阶級) + 1”这个递推，本质上就是 DAG 上的 DP。树是一种特殊的 DAG（没有横叉边），从叶子到根的计算顺序就是一种拓扑序。

推广到一般 DAG：拓扑排序确定了”谁先算、谁后算”的顺序，然后在这个顺序上跑 DP 就行了。

DAG 上 DP：为什么拓扑序是天然的 DP 顺序？

DP 的核心要求：计算 $dp[v]$ 时，它依赖的所有 $dp[u]$（其中 $u \to v$）必须已经算好。拓扑排序保证 $u$ 在 $v$ 前面——按拓扑序依次计算，每个节点的前置一定已处理。

常见的 DAG-DP 问题：

• 最长路：$dp[v] = \max_{u \to v} (dp[u] + w(u,v))$
• 路径计数：$dp[v] = \sum_{u \to v} dp[u]$
• 关键路径（任务调度）：$dp[v] = t_v + \max_{u \to v} dp[u]$

这些问题在一般图上可能无解（环会导致循环依赖），但在 DAG 上有唯一的拓扑序，DP 就能顺畅地从头算到尾。

理论 + 代码

Kahn 算法（BFS 版）

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN];
int indeg[MAXN];
vector<int> topo;

void topological_sort(int N) {
    queue<int> q;
    for (int i = 1; i <= N; i++)
        if (indeg[i] == 0) q.push(i); // ① 入度为 0 的先入队
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);            // ② 加入拓扑序列
        for (int v : adj[u]) {
            indeg[v]--;               // ③ 删掉 u 的出边
            if (indeg[v] == 0)
                q.push(v);            // ④ 新的入度 0 入队
        }
    }
    // 如果 topo.size() < N，说明有环
}

逐行解析：

• ① 入度为 0 的节点没有前置依赖，可以安全地先处理。为什么初始时一定有入度为 0 的节点？因为 DAG 中一定存在入度为 0 的节点（前面证明了）。
• ② 每次从队列取出一个节点，加入拓扑序列。队列保证了 FIFO——先发现入度为 0 的先处理。
• ③④ 删掉 $u$ 的出边：$u$ 的每个邻居 $v$ 的入度减 1。如果减到 0，说明 $v$ 的所有前置都处理完了，可以入队。

走一遍具体过程

5 个任务，依赖关系：1→3, 2→3, 2→4, 3→5, 4→5

初始入度：[0, 0, 2, 1, 2]（任务 1, 2 无依赖，任务 3 被依赖 2 次）

步骤	队列	取出	topo	更新入度
1	[1,2]	1	[1]	3的入度 2→1
2	[2]	2	[1,2]	3的入度 1→0→入队; 4的入度 1→0→入队
3	[3,4]	3	[1,2,3]	5的入度 2→1
4	[4]	4	[1,2,3,4]	5的入度 1→0→入队
5	[5]	5	[1,2,3,4,5]	—

拓扑序：1, 2, 3, 4, 5。✓

注意：拓扑序不唯一。2, 1, 4, 3, 5 也是合法的（1 和 2 之间没有依赖关系，谁先都行）。Kahn 算法给出的序取决于队列的处理顺序——如果用优先队列，可以得到字典序最小的拓扑序。

DFS 版拓扑排序

bool visited[MAXN];
bool onstack[MAXN]; // 检测环
vector<int> order;
bool has_cycle = false;

void dfs(int u) {
    visited[u] = true;
    onstack[u] = true;
    for (int v : adj[u]) {
        if (onstack[v]) { has_cycle = true; return; } // ① 回边 → 环
        if (!visited[v]) dfs(v);
    }
    onstack[u] = false;
    order.push_back(u); // ② 后序加入
}
// 拓扑序 = reverse(order)

逐行解析：

• ① onstack[v] 检测回边（back edge）：如果 $v$ 还在当前递归栈上，说明存在从 $v$ 到 $u$ 的路径（通过栈），加上 $u \to v$ 就形成环。为什么回边等价于环？因为递归栈记录了从起点到当前节点的完整路径——栈上的节点形成一条链，$u \to v$ 让链首尾相连。
• ② 后序（退出时）加入。为什么是后序而不是前序？ 前序（进入时记录）不能保证 $u$ 在 $v$ 前面——DFS 可能先进入 $u$，然后递归到 $v$，$v$ 被先记录。后序翻转后保证：如果 $u \to v$，$v$ 先被记录（DFS 会先递归到最深处），翻转后 $u$ 排在 $v$ 前面。

DAG 上 DP：关键路径

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN]; // adj[u] = {v : u→v}
int indeg[MAXN], t[MAXN], dp[MAXN];

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++) scanf("%d", &t[i]); // 每个任务的耗时
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d%d", &a, &b); // a 必须在 b 之前
        adj[a].push_back(b);
        indeg[b]++;
    }
    queue<int> q;
    for (int i = 1; i <= N; i++)
        if (indeg[i] == 0) { q.push(i); dp[i] = t[i]; } // ① 无前置
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            dp[v] = max(dp[v], dp[u] + t[v]); // ② 关键路径 DP
            if (--indeg[v] == 0) q.push(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) ans = max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}

逐行解析：

• ① 入度为 0 的任务没有前置依赖，最早完成时间 = 自身耗时 $t_i$。
• ② 对于 $v$ 的每个前置 $u$：$v$ 最早在 $u$ 完成后才能开始。取所有前置中最大的完成时间 + $v$ 自身耗时。这就是关键路径——整个项目最短完成时间取决于最长的依赖链。

这个 DP 为什么正确？ 因为拓扑序保证了处理 $v$ 时所有 $u \to v$ 的 $dp[u]$ 已经算好。没有循环依赖，不需要担心”还没算就被用到”。

例题

例题 1：TB B65 — Road to Promotion Hard

题目：$N$ 个员工，$N-1$ 条上司-下属关系（但不知道谁是上司谁是下属）。已知员工 $T$ 是社长。求每个员工的”阶级”：没有下属的员工阶级为 0，有下属的员工的阶级 = 直属下属中最大的阶级 + 1。

数据范围：$2 \le N \le 10^5$

—— AtCoder Tessoku Book B65

分析：先从 $T$ 出发 BFS 建树（确定边的方向），然后按拓扑逆序（从叶子到根）计算阶级。这是一个 DAG 上 DP。

代码：

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN]; // 无向边
vector<int> children[MAXN];
int level[MAXN], par[MAXN];

int main() {
    int N, T;
    scanf("%d%d", &N, &T);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    // ① BFS 建树：从 T 出发确定方向
    queue<int> q;
    par[T] = -1; q.push(T);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (v == par[u]) continue;
            par[v] = u;
            children[u].push_back(v);
            q.push(v);
        }
    }
    // ② 反向 BFS 序 = 拓扑逆序（叶子先处理）
    for (int i = order.size() - 1; i >= 0; i--) {
        int u = order[i];
        level[u] = 0;
        for (int v : children[u])
            level[u] = max(level[u], level[v] + 1); // ③ 阶级 = max(子阶级)+1
    }
    for (int i = 1; i <= N; i++)
        printf("%d%c", level[i], " \n"[i == N]);
    return 0;
}

逐行解析：

• ① 从社长 $T$ 出发 BFS。每条边的方向是从靠近 $T$ 的一端指向远离 $T$ 的一端。
• ② 反向遍历 BFS 序 = 按深度从大到小 = 叶子先处理。
• ③ 阶级 = 子节点中最大阶级 + 1。

---

例题 2：DAG 上 DP——任务调度

场景：$N$ 个任务，$M$ 个前置关系（$a_i$ 必须在 $b_i$ 之前完成）。每个任务耗时 $t_i$。求完成所有任务的最短总时间。

数据范围：$1 \le N \le 10^5$，$1 \le M \le 10^5$

分析：拓扑排序 + 关键路径 DP。按拓扑序依次处理，每个节点最早完成时间 = 所有前置中最晚完成时间 + 自身耗时。

代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 100006;
vector<int> adj[MAXN];
int indeg[MAXN], t[MAXN], dp[MAXN];

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++) scanf("%d", &t[i]);
    for (int i = 0; i < M; i++) {
        int a, b; scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        indeg[b]++;
    }
    queue<int> q;
    for (int i = 1; i <= N; i++)
        if (indeg[i] == 0) { q.push(i); dp[i] = t[i]; } // ① 无前置，直接开始
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            dp[v] = max(dp[v], dp[u] + t[v]); // ② 关键路径转移
            if (--indeg[v] == 0) q.push(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) ans = max(ans, dp[i]);
    printf("%d\n", ans);
}

逐行解析：

• ① 入度为 0 的任务没有前置依赖，最早完成时间就是自身耗时 $t_i$。
• ② $v$ 的每个前置 $u$ 完成后 $v$ 才能开始。取所有前置中最晚的完成时间 + $t_v$。

模拟：5 个任务，耗时 $t = [3, 2, 4, 1, 5]$，依赖 1→3, 2→3, 2→4, 3→5, 4→5。

拓扑序：1, 2, 3, 4, 5。

• dp[1] = 3, dp[2] = 2
• dp[3] = max(3+4, 2+4) = 7
• dp[4] = 2+1 = 3
• dp[5] = max(7+5, 3+5) = 12

答案 = 12。关键路径：2→3→5。

---

例题 3：T90 035 — Preserve Connectivity（★7，虚树）

题目：$N$ 个节点的树。$Q$ 个查询，每个查询给 $K$ 个节点，求同时连接这 $K$ 个节点的最小连通子树的边数。

数据范围：$2 \le N \le 2 \times 10^5$，$\sum K_i \le 2 \times 10^5$

—— AtCoder Typical 90 035

分析：★7 难题。关键思路是构建虚树（Virtual Tree）——只保留查询中涉及的 $K$ 个节点及其 LCA，压缩树的规模。

最小连通子树的边数 = $\lfloor\text{按 DFS 序排列后相邻节点距离之和} / 2 \rfloor$。

具体步骤：

1. 预处理 LCA（倍增法）
2. 对查询的 $K$ 个节点按 DFS 序排序
3. 计算相邻节点（包括首尾）的 LCA 距离之和，除以 2

// 核心公式
// 设按 DFS 序排序后的节点为 v_1, v_2, ..., v_K
// 子树边数 = (dist(v_1,v_2) + dist(v_2,v_3) + ... + dist(v_{K-1},v_K) + dist(v_K,v_1)) / 2

（★7 练习题，完整实现需要 LCA 预处理。）

---

例题 4：T90 062 — Paint All（★6）

题目：$N$ 个白球和 $N$ 个道具。道具 $i$ 只有在球 $A_i$ 或球 $B_i$ 至少有一个是白色时才能使用，使用后把球 $i$ 涂黑。求是否能让所有球变黑。

—— AtCoder Typical 90 062

分析：这是一个拓扑排序的变体。把每个球看作节点。道具 $i$ 的前置条件是”球 $A_i$ 或球 $B_i$ 至少有一个是白色”——即”球 $A_i$ 和球 $B_i$ 不能都已变黑”。

换个角度：道具 $i$ 可以使用 ⟺ 球 $A_i$ 还是白色 或 球 $B_i$ 还是白色。当道具 $i$ 使用后，球 $i$ 变黑。

这可以建模为一个图论问题：以球为节点，道具为边。每次选一个道具，使用后该球变黑。贪心策略：模拟执行过程，每次检查哪些道具现在可用（条件满足），选择使用。如果最终所有球变黑则有解。

可以用 BFS 模拟：初始所有球白色，把所有满足条件的道具入队。使用道具 $i$ 后，球 $i$ 变黑，可能解锁新的道具。

代码：

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 200006;
vector<int> ball_to_item[MAXN]; // ball_to_item[b] = 使用球 b 的道具列表
int A[MAXN], B[MAXN];
bool black[MAXN]; // 球是否已变黑

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) scanf("%d%d", &A[i], &B[i]);
    for (int i = 1; i <= N; i++) {
        ball_to_item[A[i]].push_back(i); // ① 道具 i 使用球 A[i]
        ball_to_item[B[i]].push_back(i); // ② 道具 i 也使用球 B[i]
    }
    // ③ 初始化：所有球白色，检查哪些道具可用
    vector<int> remaining(N + 1, 2); // remaining[i] = 道具 i 还需要几个白球
    queue<int> q;
    for (int i = 1; i <= N; i++)
        if (remaining[i] > 0) { remaining[i] = 2; } // 每个道具初始需要 2 个白球
    // 这里的逻辑稍有不同：道具 i 需要球 A[i] 或 B[i] 是白的
    // 简化处理：直接模拟
    fill(black, black + N + 1, false);
    // 初始哪些道具可用？A[i] 或 B[i] 是白色——初始全白，所以全部可用
    // 但每个道具用完后涂黑球 i
    // 用 set 或队列管理“可用的道具”
    vector<bool> used(N + 1, false);
    queue<int> que;
    for (int i = 1; i <= N; i++) que.push(i); // ④ 初始全部可用
    while (!que.empty()) {
        int item = que.front(); que.pop();
        if (used[item]) continue;
        if (black[A[item]] && black[B[item]]) continue; // ⑤ 两个球都黑了，道具不可用
        // ⑥ 使用道具 item，涂黑球 item
        used[item] = true;
        black[item] = true;
        // ⑦ 球 item 变黑后，检查哪些新道具可能变得可用
        for (int ni : ball_to_item[item])
            if (!used[ni]) que.push(ni);
    }
    int cnt = 0;
    for (int i = 1; i <= N; i++) if (used[i]) cnt++;
    printf("%s\n", cnt == N ? "Yes" : "No");
}

逐行解析：

• ①② 预处理：每个球被哪些道具依赖。
• ④ 初始所有球都是白色，所有道具都可用，全部入队。
• ⑤ 如果道具 $i$ 的两个依赖球都变黑了，道具不可用，跳过。
• ⑥ 使用道具 $i$，把球 $i$ 涂黑。
• ⑦ 球 $i$ 变黑后，依赖球 $i$ 的其他道具可能条件变了，重新入队检查。

复杂度：每个道具最多入队 $O(\text{度数})$ 次，总时间 $O(N)$。

参考文献

教材讲解 — 競技プログラミングの鉄則 第 9 章

• 9.5 树上 DFS（B65 Road to Promotion Hard 解说）

系统练习 — 競技プログラミングの鉄則

• B65 Road to Promotion Hard（树上 DFS/拓扑序）【例题】

实战练习 — 競プロ典型 90 問

• 035 Preserve Connectivity（★7，虚树）【例题】
• 062 Paint All（★6，模拟/拓扑排序）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化