第 30 章结尾我写了这么一句：
拓扑排序其实还是 BFS，只是「什么时候能入队」的条件变了。 副产品：队列空了却还有点没出来 = 图里有环。
这一章要做的就是把这两句话落到实处。而且这一章还有一件前 30 章都没碰到过的麻烦：
⚠ 答案不唯一。 同一张图往往有几十上百个都对的顺序 —— 而对拍是逐字节比字符串的。
第 7 步会正面处理它，那一节的收获（验证器）以后每次遇到「答案不唯一」都要用上。
1 一句话问题
有
n个任务和m条依赖，每条写成u v，意思是「u 必须排在 v 前面」。 （⚠ 可能有重边，也可能有自环。）
- 如果根本排不出来，输出
-1；- 否则输出一个合法的顺序 —— 有多个合法顺序时，输出字典序最小的那个。
题面本来只需要说「输出一个合法顺序」。加上「字典序最小」纯粹是为了把答案钉唯一 —— 否则你和标准答案各给一个都对的顺序，对拍会判你错。
第 7 步会看到另一条出路（写验证器），以及为什么这一章两条都用上了。 遇到答案不唯一的题，先想清楚怎么验，再动手写。
2 手算一遍：6 个任务、6 条依赖
6 6
5 1 ┐
5 3 ├ 5 → 1 → 3（外加一条 5 → 3）
1 3 ┘
6 4 ┐
6 2 ├ 6 → 4 → 2（外加一条 6 → 2）
4 2 ┘画出来是两条互不相干的链：5 → 1 → 3 和 6 → 4 → 2
（每条链上还多了一条「跨一格」的边，那是故意的，第 8 步会用到）。
一上来谁也不欠的只有 5 号和 6 号。既然要字典序最小，就先做 5：
| 这一步能做的 | 挑谁 | 已排好 |
|---|---|---|
| 5、6 | 5 | 5 |
| 1、6 | 1 | 5 1 |
| 3、6 | 3 | 5 1 3 |
| 6 | 6 | 5 1 3 6 |
| 4 | 4 | 5 1 3 6 4 |
| 2 | 2 | 5 1 3 6 4 2 |
5 1 3 6 4 2 —— 这组数后面每一步都会回来验。
⚠ 请特别注意它不是 1 2 3 4 5 6。这也是故意的 —— 第 11 步会看到，
如果数据里「编号顺序本身就是合法答案」，一整批错法会集体隐身。
3 暴力：不用队列、不用入度数组，每一轮从头扫一遍
点「运行 ▶」看结果
想法朴素得不能再朴素，就是第 2 步那张表的直译：
一轮一轮地挑人。每一轮扫描所有还没被挑走的任务，看它的前驱是不是全都被挑走了 —— 是的话它现在就能做；在所有能做的里面挑编号最小的。 某一轮一个都挑不出来 → 剩下的人互相卡住 → 有环 →
-1。
- 暴力：「能不能做」每一轮都现算（把前驱重新问一遍）；
- 正解：给每个点记一个
in[v]，增量维护（减一、减一、减到 0）。
一个现算、一个增量维护 —— 不是同一个想法写两遍，所以它们不太可能一起错 （第 9 章那条规矩）。
顺带把有环那张也跑一遍，-1 那一支从一开始就要在场：
4 实测：暴力慢在哪
暴力每挑一个人，就要把所有人重新问一遍 —— O(n × (n + m))，n 一翻倍它就四倍地慢。
本机实测（./genBig <n>，边数取 2n，固定种子）：
| 命令 | 任务数 n | 暴力（每轮从头扫） | Kahn + 小根堆 |
|---|---|---|---|
./genBig 10000 | 1 万 | 0.20 秒 | 0.01 秒 |
./genBig 20000 | 2 万 | 0.80 秒 | 0.02 秒 |
./genBig 40000 | 4 万 | 3.80 秒 | 0.03 秒 |
./genBig 80000 | 8 万 | 17.43 秒 | 0.07 秒 |
./genBig 160000 | 16 万 | 89.07 秒 | 0.15 秒 |
★ n 翻一倍，暴力慢四倍，正解只慢一倍。 16 万个任务时差了近 600 倍。
genBig 的边数我一开始想取小一点（n/5），好让数据小到网页那个「同题对比」小工具
也传得动（本地运行服务对输出有 64 KB 的上限，第 30 章刚为它吃过亏）。
实测发现不行：边一少，暴力里那句「找到第一个能做的就停」几乎立刻命中 ——
n = 20000 时它只要 0.10 秒，比 m = 2n 时快了八倍。
暴力又一次假装自己不慢，这次让它偷懒的是「提前 break」。
所以这张表老老实实用 m = 2n，而且只能在终端里跑（数据传不进网页）：
g++ -O2 -std=c++17 -o genBig genBig.cpp && g++ -O2 -std=c++17 -o brute brute.cpp
g++ -O2 -std=c++17 -o fast fast.cpp
./genBig 40000 > big.txt
time ./brute < big.txt > /dev/null # 3.8 秒
time ./fast < big.txt > /dev/null # 0.03 秒5 ★ 关键一步：入度减到 0 才能入队
点「运行 ▶」看结果
| 第 30 章的 BFS | 这一章的拓扑排序 | |
|---|---|---|
| 能入队的条件 | 没来过 | 所有前驱都已经出队了 |
| 容器 | 队列 | 队列（要字典序最小就换成小根堆） |
| 出队之后干什么 | 把邻居入队 | 把后继的入度减一，减到 0 的入队 |
而「所有前驱都出队了」这件事不需要每次去数：
给每个点记一个 in[v]（还欠着几个前驱），一个前驱出队就给它的所有后继减一 ——
for (int v : g[u])
if (--in[v] == 0) q.push(v); // ★ 减到 0，才轮到它★ 注意这句话的形状：「依赖谁，就先填谁」。 第 21 章是 DP 的填表顺序、第 26 章是区间、第 27 章是后序遍历、第 28 章是 S 从小到大 —— 这是它第六次登场，而这一次它以最直白的样子出现：
拓扑序就是「依赖顺序」这四个字本身。 前面那五章其实都在做拓扑排序，只是那些图太规整，顺序一眼就能看出来，用不着真的排。
if ((int)ans.size() < n) { cout << -1 << "\n"; return 0; }就这一句，判环就做完了。为什么它是对的，两句话：
- 剩下的那些点，每一个都还欠着至少一个前驱；
- 顺着「谁欠谁」一直往回走，点是有限的，早晚会踩回一个来过的点 —— 那就是一个环。
反过来也成立：有环的话，环上的点谁也别想把入度减到 0，他们注定卡在原地。
判环不用另写一份代码，它就是「出队够不够 n 个」这一个数字。
⚠ 而正因为它是白送的，它也是最容易被漏掉的 —— 白送到你注意不到自己没接住。
第 8 步那个 wrongNoCycle.cpp 就是这么来的。
6 动画：入度一个个减下去
点上面那个数字是它还欠着几个前驱，减到 0 就变绿、进容器。 右边那个大数字是 ★ 还没出来的点数 —— 队列空了它还不是 0，就说明有环。
按一下「换成有环那张」（在默认图上加一条 3 → 5），你会看到 5、1、3 三个点
入度永远降不到 0，队列早早就空了，计数器停在 3。那就是判环的全部现场。
下拉框里那四个错误版本，第 8 步逐个讲。
7 ★ 答案不唯一 —— 这一章真正的新东西
先看另一种完全不同的拓扑排序：DFS 的后序逆序。
点「运行 ▶」看结果
它跑出 6 5 4 2 1 3 —— 和正解 5 1 3 6 4 2 完全不一样。
但两个都是对的。
「不唯一」是个含糊的词。数一下：
点「运行 ▶」看结果
20 个。 而且这个 20 是可以心算的：默认那张图是两条互不相干的链
（5→1→3 和 6→4→2），把它们交错排进 6 个位置，就是「从 6 个位置里挑 3 个给第一条链」——
C(6,3) = 20★ 数它用的是第 28 章那套状压 DP：
f[S] = 把集合 S 里的任务排成一个合法前缀，有多少种排法
转移：枚举下一个做谁（v ∉ S，且 v 的所有前驱都在 S 里），f[S | 1<<v] += f[S]填表顺序还是「S 从小到大」，理由和第 28 章一字不差（S | (1<<v) 一定比 S 大）。
顺带，判环在这里也是白送的：有环时环上的点永远凑不齐前驱，全集根本到不了，答案自然是 0。
这棵树把「不唯一」摊开给你看：每一层是「这一步可以做谁」，每一条从上到下的路径都是一个正确答案， 一共 20 条。蓝色那条是「每一步都挑编号最小的分支」走出来的 —— 那就是字典序最小的答案， 也正是小根堆干的事。（第 3 章那句「递归 = 决策树」在这里第二次登场。）
出路一：把答案钉唯一。 题面加一句「输出字典序最小的那个」，
代码里把队列换成小根堆。好处是能直接逐字节对拍；
代价是多了一层和拓扑排序本身无关的东西（而且慢了个 log n）。
出路二：不比答案，比性质。 写一个验证器，只问「你给的这个顺序合不合法」：
点「运行 ▶」看结果
它只查两件事，缺一不可：
① 必须正好是 1..n 的一个排列；② 每一条依赖都得是「前面指向后面」。
上面这一组查的就是 dfsTopo.cpp 给的那个顺序 —— 它跟正解不一样，但合法。
⚠ 验证器有个必须记住的盲区：它只能证明「这个答案合法」，
不能证明「答案存在时你没漏报」 —— 一份永远输出 -1 的程序能通过所有合法性检查。
所以判环的结论还得单独对一遍。
（这和第 20 章那句「对拍只能证伪」是同一件事的另一面。）
本章两条出路都用上了：主对拍走出路一（brute vs fast，逐字节比），
而 dfsTopo.cpp 走出路二 —— check:viz 每轮都拿验证器验它一遍，
再单独核对它的判环结论和 Kahn 一致。
8 四种把它写错的方式
点「运行 ▶」看结果
跑出 5 6 1 4 3 2。★ 这一份特殊：它给的顺序完全合法，验证器查都查不出问题 —— 它只是不是题目要的「字典序最小」那个。
把它留着，是因为它一个人就把这一章两件事都说清了： 拓扑序不唯一，所以题面必须把答案钉唯一。
点「运行 ▶」看结果
跑出 5 6 1 3 4 2。第 30 章刚讲过「vis 要在入队时打」，这里正好反过来 ——
记答案必须在出队时。两句话不打架，说的是同一件事：
- 入队时打
vis：是为了「别让同一个点被塞两次」，越早越好； - 出队时记答案：因为顺序是出队决定的，不是入队决定的。
⚠ 用普通队列时这两者恰好一样（先进先出，入队序 = 出队序），所以这个 bug 会隐身； 一换成小根堆，堆把队列重排了一遍，进去的顺序和出来的顺序当场分家。 这也解释了它为什么在第 30 章那种纯 BFS 里从来不出问题 —— 那里根本没有堆。
点「运行 ▶」看结果
跑出 5 1 3 3 6 2 4 2 —— 8 个数，还有重复。
if (--in[v] == 0) q.push(v) 写成了 --in[v]; q.push(v);，
等于把「所有前驱都满足」偷偷降级成了「满足一个就行」。
⚠ 有一类图完全抓不到它：每个点最多只有一个前驱（一棵树、一条链）—— 那时两句话是同一个意思。所以默认那张图里，3 号和 2 号各有两个前驱，那两条「跨一格」的边就是为它准备的。
点「运行 ▶」看结果
跑出 2 3 1 4 5 6 —— 算法一点毛病没有，错的是读题。 把它丢给验证器，6 条依赖全部被违反：
★ 请注意它过得了验证器的第一关（是 1..6 的排列，长度也对）。
这就是验证器为什么必须查两件事，而不是只查「是不是排列」。
点「运行 ▶」看结果
在有环那张图上跑出 6 4 2 —— 只有 3 个数。它少的就是那句
if (ans.size() < n) 输出 -1。只要图是 DAG，它就完全正确 ——
这也正是它最危险的地方，第 11 步会看到它的死活完全捏在生成器手里。
9 ★ 一块试金石：什么都不做
点「运行 ▶」看结果
它不是一个真实的 bug —— 没人会不小心写出这个。它是一块试金石：
在默认那张图上它输出 1 2 3 4 5 6，一眼就错。可是 ——
如果生成器造 DAG 时只连「编号小 → 编号大」的边（这是最省事的造法， 也几乎是每个人的第一反应），那么数据就白送了一条题目里没有的性质：
编号本身就是一个合法拓扑序，而且正好是字典序最小的那个。
于是这份「什么都不做」的代码 300 轮全对。 一批连「什么都不做」都打不假的数据，你还能指望它验出什么呢？
修法只有一处，而且不改图的形状，只改名字：
先随机一个排列 perm，再连 perm[i] → perm[j]（i < j）。
它立刻从 0 / 300 变成 265 / 300。
这一招和第 27 章「打乱树的点编号」是同一个动作： 别让编号自己带上一层题目没给的含义。
10 ★ 对拍
300 轮实测，六个版本：
| 故意写错的地方 | 被抓 | 第几轮 |
|---|---|---|
| 方向读反 | 236 / 300 | 第 1 轮 |
| 没减到 0 就入队 | 235 / 300 | 第 1 轮 |
| 什么都不做（试金石） | 211 / 300 | 第 2 轮 |
| 用普通队列 | 156 / 300 | 第 2 轮 |
| 入队时就记答案 | 156 / 300 | 第 2 轮 |
| 忘了判环 | 64 / 300 | 第 4 轮 |
（最后一行的 64 正好等于「这 300 轮里有 64 轮是有环的」—— 它只在有环时才可能出错， 所以 64 / 64，一轮不漏。）
11 ★ 生成器调了四次，每次只改一处
gen.cpp 带了五个档位（./gen 种子 档位）。种子固定 1..300：
| 档位 | 改了什么 | 有环轮数 | 什么都不做 | 忘了判环 | 普通队列 | 提前入队 | 方向反 | 入队就记 |
|---|---|---|---|---|---|---|---|---|
| 0（最初） | 编号不打乱 + 只连小→大 | 0 | 0 | 0 | 193 | 258 | 300 | 193 |
| 1 | 打乱编号 | 0 | 265 | 0 | 196 | 257 | 300 | 196 |
| 2 | 允许成环：每条边 1/3 反向、自环随便造 | 231 | 60 | 231 | 46 | 161 | 69 | 46 |
| 3 | 改成每三组挑一组允许成环 | 207 | 76 | 207 | 64 | 208 | 93 | 64 |
| 4（在用） | 自环也只在那一组里留 | 64 | 211 | 64 | 156 | 235 | 236 | 156 |
档位 0 → 1：只改了「给点换个名字」这一处 —— 图的形状一条边都没动 —— 「什么都不做」从 0 跳到 265。这是第 27 章那个坑的第五张脸。
档位 2 → 3 → 4：这是一个前面几章没遇到过的新毛病。
★ 前面四章踩的都是「某一支永远走不到」（-1 那一支、多连通块那一支）。
档位 2 一上来矫枉过正：300 轮里 231 轮都有环，而有环时所有程序一律输出 -1 ——
于是三个跟顺序有关的 bug 反而没机会现形（46 / 161 / 69）。
档位 3 把「允许成环」从「每条边」降到「每三组挑一组」，只涨了一点点（207 轮还是太多）；
一查才发现大头是自环 —— n 只有几个的时候，随手就撞出一条「我必须排在我自己前面」。
档位 4 把自环也关进那一组，有环降到 64 / 300，三个顺序 bug 立刻涨到 156 / 235 / 236。
每一支都要有，而且都不能多到吃掉别人。 「某一支永远走不到」和「某一支占得太多」，是同一枚硬币的两面。
拿 genNice.cpp（编号就是拓扑序 + 永远无环）跑 300 轮：
| 什么都不做 | 忘了判环 | 普通队列 | 提前入队 | 方向反 | |
|---|---|---|---|---|---|
| genNice | 0 | 0 | 210 | 242 | 296 |
| 最终档 | 211 | 64 | 156 | 235 | 236 |
看最后一列：「方向读反」在温柔数据上反而抓得更准（296 vs 236）。
道理不难想 —— 数据里只有「小 → 大」的边，读反之后答案从 1 2 3 … 变成 … 3 2 1，
差得不能再明显；而在打乱编号的数据里，反过来的那个顺序反倒有可能碰巧也合法。
所以「换了生成器，抓获率整体变好」这种话是靠不住的， 必须一个 bug 一个 bug 地看。第 27 章那笔「档位 3 反而少抓三十几轮」的账， 第 30 章那笔「打散连通性反而让另外两个掉了」的账，都是同一回事： 要的是把 0 变成非 0，不是让平均分好看。
12 这一章可以带走的四样东西
【1】拓扑排序就是换了入队条件的 BFS。
BFS： 没来过 → 入队
拓扑排序： 所有前驱都出队了 → 入队（记 in[v]，减到 0 就是）而「依赖谁就先填谁」这句话，从第 21 章一路走到这里，第六次登场 —— 拓扑序就是「依赖顺序」这四个字本身。
【2】判环是白送的：队列空了，出队却不够 n 个。 剩下的人每个都还欠着前驱，顺着「谁欠谁」往回走一定会踩回来 —— 那就是环。 ⚠ 正因为白送，它也最容易被漏掉。
【3】答案不唯一时，先想清楚怎么验，再动手写。 两条出路： 把答案钉唯一（小根堆 + 「字典序最小」），或者写验证器（查排列 + 查每条边前指后）。 ⚠ 验证器的盲区：它证明不了「答案存在时你没漏报」，判环的结论得单独对。
【4】生成器的两头都要看。 既不能让某一支永远走不到（编号就是拓扑序 / 永远无环 → 两个 bug 全是 0 / 300）， 也不能让某一支占得太多（231 轮都有环 → 顺序类的 bug 全被挤没）。 调的时候一次只改一处、每次都实测，而且每一档都留成参数，让读者能整张表重跑。
第 32 章：最短路一 —— Dijkstra。
第 30 章的 BFS 已经能求最短路了，但那是每条边都一样长的情况。 边一带上权，「一圈一圈往外扩」就不成立了 —— 走三条短边可能比走一条长边还近。
★ 关键一步是一个贪心：每次取「当前最近的、还没定下来的点」，它的距离当场就定死了。 为什么这个贪心是对的（接阶段 4 那套交换论证），以及为什么有负权边就不行 —— 下一章会把这两件事讲透，而且照例拿一份完全不同思路的代码（Floyd）来对拍。
顺带你会发现：把这一章的小根堆原样搬过去，就是「堆优化 Dijkstra」。 容器换了，套路一点没变。
13 自测
- 洛谷 B3644 【模板】拓扑排序 —— 本章模板题。写完对着 fast.cpp 逐行检查一遍
- 洛谷 P1113 杂务 —— ★ 拓扑序 + DP：每个任务的最早完成时间。第 21 章那句「依赖谁就先填谁」在这里字面成立
- 洛谷 P1347 排序 —— ★ 边一条一条加进来，每加一条就判一次「已确定 / 有矛盾 / 还不确定」。逼你想清楚「拓扑序唯一」是什么意思
- 洛谷 P4017 最大食物链计数 —— 拓扑序上做计数 DP。答案要取模，正好复习第 42 章要讲的那些坑
- 洛谷 P1983 [NOIP2013 普及组] 车站分级 —— 进阶：难点全在建图上，边要靠「虚点」来省。建完图之后就是模板
- 洛谷 P2712 摄像头 —— 判环 + 拓扑删点。编号很大要离散化，是很好的综合练习