InoueMoby's Blog

前言

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

把每门课看成一个节点，先修关系看成有向边（ $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 算法的流程：

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

为什么这样一定能得到合法的拓扑序？ 因为每次放入序列的节点入度为 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

分析：关键观察——把查询的 $K$ 个节点按 DFS 序排列为 $v_1, v_2, \ldots, v_K$ ，则最小连通子树的边数等于：

$\frac{\text{dist}(v_1,v_2) + \text{dist}(v_2,v_3) + \cdots + \text{dist}(v_{K-1},v_K) + \text{dist}(v_K,v_1)}{2}$

为什么？想象沿着排序后的节点走一圈（ $v_1 \to v_2 \to \cdots \to v_K \to v_1$ ），每条子树边恰好被走过两次（上去一次、下来一次），所以总距离除以 2 就是边数。

需要 LCA（最近公共祖先）来快速计算树上两点距离： $\text{dist}(a,b) = \text{depth}[a] + \text{depth}[b] - 2 \cdot \text{depth}[\text{lca}(a,b)]$ 。

代码：

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

const int MAXN = 200006, LOG = 18;
vector<int> adj[MAXN];
int dep[MAXN], par[MAXN][LOG], euler[MAXN], ein;

void dfs(int u, int p) {
    par[u][0] = p;
    euler[u] = ein++;                    // ① DFS 序
    for (int v : adj[u])
        if (v != p) { dep[v] = dep[u] + 1; dfs(v, u); }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int diff = dep[a] - dep[b];
    for (int k = 0; k < LOG; k++)       // ② 把 a 提到和 b 同一层
        if (diff >> k & 1) a = par[a][k];
    if (a == b) return a;
    for (int k = LOG - 1; k >= 0; k--)  // ③ 一起往上跳
        if (par[a][k] != par[b][k]) { a = par[a][k]; b = par[b][k]; }
    return par[a][0];
}

int dist(int a, int b) { return dep[a] + dep[b] - 2 * dep[lca(a, b)]; }

int main() {
    int N;
    scanf("%d", &N);
    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);
    }
    dep[1] = 0; dfs(1, 0);
    for (int k = 1; k < LOG; k++)        // ④ 倍增预处理
        for (int i = 1; i <= N; i++)
            par[i][k] = par[par[i][k-1]][k-1];

    int Q; scanf("%d", &Q);
    while (Q--) {
        int K; scanf("%d", &K);
        vector<int> vs(K);
        for (int i = 0; i < K; i++) scanf("%d", &vs[i]);
        sort(vs.begin(), vs.end(), [](int a, int b) { return euler[a] < euler[b]; }); // ⑤ 按 DFS 序排序
        int ans = 0;
        for (int i = 0; i < K; i++)
            ans += dist(vs[i], vs[(i + 1) % K]);    // ⑥ 相邻距离求和
        printf("%d\n", ans / 2);                      // ⑦ 除以 2
    }
}

逐行解析：

① DFS 预处理：记录每个节点的 DFS 序和深度。
②③ 倍增法 LCA：先对齐深度，再一起往上跳。
④ 倍增表预填充： $par[i][k] = par[par[i][k-1]][k-1]$ 。
⑤ 按 DFS 序排序查询节点。
⑥ 计算排序后相邻节点（含首尾）的距离之和。
⑦ 每条边被走过两次，除以 2 得到边数。

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

题目： $N$ 个白球和 $N$ 个道具，编号 1 到 $N$ 。道具 $i$ 只有在球 $A_i$ 或球 $B_i$ 至少有一个是白色时才能使用，使用后把球 $i$ 涂黑。如果能涂完所有球，输出道具使用顺序（每行一个编号），否则输出 -1。

—— AtCoder Typical 90 062

分析：逆向思考。最终所有球都黑了。逆序看：从”全黑”状态出发，逐步”undo”道具，让球变白。

“undo 道具 $i$ ” = 把球 $i$ 变白。在正向中，使用道具 $i$ 时球 $i$ 还是白的（因为道具 $i$ 涂黑球 $i$ ），所以如果 $A_i = i$ 或 $B_i = i$ （自引用），条件天然满足。

逆向 BFS：初始所有球黑。道具 $i$ 可以被 undo，如果 $A_i$ 或 $B_i$ 已经是白的（被之前的 undo 操作变白），或者 $A_i = i$ 或 $B_i = i$ （自引用，正向中球 $i$ 使用时还未被涂黑）。undo $i$ 后球 $i$ 变白，通知依赖球 $i$ 的道具重新检查。

代码：

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

int N, A[200006], B[200006];
vector<int> b2i[200006]; // 依赖球 b 的道具列表
bool black[200006], done[200006];

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d%d", &A[i], &B[i]);
        b2i[A[i]].push_back(i);
        b2i[B[i]].push_back(i);
        black[i] = true;   // ① 最终状态：全部黑
    }

    queue<int> q;
    // ② 初始种子：自引用的道具（A[i]=i 或 B[i]=i）
    for (int i = 1; i <= N; i++)
        if (A[i] == i || B[i] == i) q.push(i);

    vector<int> rev_order;
    while (!q.empty()) {
        int item = q.front(); q.pop();
        if (done[item]) continue;
        // ③ 检查条件：A[item] 已白 或 B[item] 已白 或自引用
        bool a_ok = !black[A[item]] || A[item] == item;
        bool b_ok = !black[B[item]] || B[item] == item;
        if (!a_ok && !b_ok) continue;
        done[item] = true;
        black[item] = false;   // ④ undo：球 item 变白
        rev_order.push_back(item);
        for (int ni : b2i[item])   // ⑤ 通知依赖球 item 的道具
            if (!done[ni]) q.push(ni);
    }

    if ((int)rev_order.size() == N) {
        for (int i = rev_order.size() - 1; i >= 0; i--)
            printf("%d\n", rev_order[i]);  // ⑥ 逆序输出 = 正向使用顺序
    } else {
        printf("-1\n");
    }
}

逐行解析：

① 逆向模拟从”全黑”开始。
② 自引用道具是逆向的起点：正向中使用道具 $i$ 时球 $i$ 还白，所以自引用条件天然成立。
③④ undo 道具 $i$ ：条件球中至少一个已经是白的（被之前的 undo 变白），或者自引用。
⑤ 球 $i$ 变白后，依赖球 $i$ 的道具条件可能满足，重新入队。
⑥ 收集的是逆序，需要翻转输出。

参考文献

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

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

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

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

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

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

竞技编程 04-04 拓扑排序

大学选课的顺序怎么排？DAG 上的线性排列，以及 DAG-DP 的天然计算顺序

前言

问题的本质

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

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

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

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

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

理论 + 代码

Kahn 算法（BFS 版）

走一遍具体过程

DFS 版拓扑排序

DAG 上 DP：关键路径

例题

例题 1：TB B65 — Road to Promotion Hard

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

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

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

参考文献

系列索引

竞技编程 04-04 拓扑排序