专题：拓扑排序与 DAG —— 把”谁先谁后”排出来

本讲定位：图论系列第四讲，也是前三讲的遍历与后面所有 DAG 递推之间的枢纽。01～03 讲的 DFS/BFS 都不关心”先访问谁”，本讲第一次把顺序本身当成要求解的东西：有向无环图（DAG）上存在一种线性顺序，使每条边都从前指向后，这就是拓扑序。它的真正价值不在”排个序”，而在于它让”沿着边递推”成为合法操作——这正是 dp-series/08 里 DAG 上 DP 的前提。本讲做了七组实测：Kahn 与 DFS 逆后序在 5000 组随机图上判环结论完全一致、产生的序全部合法；朴素”每轮全表扫描”在 $n=2\times10^5$ 上要 77.19 秒，Kahn 只要 0.0069 秒（11187 倍）；DFS 逆后序法在链状图上 8 MB 栈只能撑 13 万层；“字典序最小的拓扑序”和”让 1 号尽量靠前”是两个不同的问题，用错做法在随机数据上错 36.8%；P4017 的分层构造下真实答案有 101 位，int 和 unsigned long long 双双溢出成 0；P1983 车站分级直接连边最坏 2.495 亿条边（约 1.9 GB），虚拟结点法压到 99.9 万条（249.7 倍），两法在 7300 组自洽数据上答案一致。文中所有代码经 g++ -O2 -std=c++14 -Wall 编译运行，B3644、P4017、P1983 三道例题均与洛谷官方样例逐一核对通过。

前置知识：第 01 讲的邻接表存图（vector 版即可）与第 7 节的 BFS 队列模板（Kahn 算法就是一个”入度版 BFS”）、DFS 递归模板；第 02 讲的递归爆栈风险（第 3 节会用到那个阈值）。不需要第 03 讲。

适合对象：第 2、3、5 节标 J，是 CSP-J 复赛的必备基本功，B3644 与 P1113 属于送分题；第 4 节（字典序与唯一性）标 S；第 6 节（车站分级建模）标 S，是 NOIP 普及组压轴的经典形态，J 组冲一等的同学建议啃下来。

1. 从一道排课表说起

问题：有 $n$ 门课，某些课之间有先修关系（学 A 才能学 B）。请给出一个学习顺序，使每门课都排在它所有先修课之后。

这个问题的模型是现成的：每门课一个点，“A 是 B 的先修课”连一条有向边 $A \to B$。要找的顺序，就是把所有点排成一行，使每条边都从左指向右。

先想一个最直白的做法：

反复扫描所有课，找一门”先修课都已经学完”的课，学掉它，重复 $n$ 次。

“先修课都已经学完”怎么判断？给每个点记一个入度（指向它的边数），入度为 0 就说明没有未完成的先修课。学掉一门课，就把它所有出边指向的点入度减 1。

这个思路完全正确，写出来是这样：

for (int step = 1; step <= n; step++) {
    int pick = -1;
    for (int u = 1; u <= n; u++)              // 每轮都把 n 个点从头扫一遍
        if (!used[u] && deg[u] == 0) { pick = u; break; }
    if (pick < 0) break;                       // 找不到了
    used[pick] = true;  printf("%d ", pick);
    for (int v : g[pick]) deg[v]--;
}

卡在哪：每轮都要从头扫 $n$ 个点，总共 $n$ 轮，光是扫描就 $O(n^2)$。实测（随机 DAG，-O2）：

$n = 2 \times 10^5$ 时差了 11187 倍。而 $n \le 10^5$ 是本讲练习题里最常见的数据范围。

浪费在哪里？每轮都重新扫全表，但上一轮之后，入度发生变化的只有”刚学掉那门课的后继”。其他点的入度一个字都没变，却被反复检查了 $n$ 次。

修掉这个浪费的办法很简单：谁的入度刚刚变成 0，就把谁记下来。用什么记？队列。这就是 Kahn 算法。

2. Kahn 算法：入度队列法

2.1 模板

// 前置：g[u] 是 u 的出边表，deg[v] 是 v 的入度（建图时顺手统计）
vector<int> topo;                       // 拓扑序结果
queue<int> q;
for (int u = 1; u <= n; u++)
    if (deg[u] == 0) q.push(u);         // 所有入度为 0 的点先入队

while (!q.empty()) {
    int u = q.front(); q.pop();
    topo.push_back(u);                  // 出队顺序 = 拓扑序
    for (int v : g[u])
        if (--deg[v] == 0) q.push(v);   // 关键：减完之后恰好为 0 才入队
}

if ((int)topo.size() < n) { /* 有环 */ }