拓扑排序

而「所有前驱都出队了」这件事不需要每次去数： 给每个点记一个 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 就是这么来的。

「不唯一」是个含糊的词。数一下：

点「运行 ▶」看结果

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。

出路一：把答案钉唯一。 题面加一句「输出字典序最小的那个」， 代码里把队列换成小根堆。好处是能直接逐字节对拍； 代价是多了一层和拓扑排序本身无关的东西（而且慢了个 log n）。

出路二：不比答案，比性质。 写一个验证器，只问「你给的这个顺序合不合法」：

点「运行 ▶」看结果

它只查两件事，缺一不可： ① 必须正好是 1..n 的一个排列；② 每一条依赖都得是「前面指向后面」。

上面这一组查的就是 dfsTopo.cpp 给的那个顺序 —— 它跟正解不一样，但合法。

⚠ 验证器有个必须记住的盲区：它只能证明「这个答案合法」， 不能证明「答案存在时你没漏报」 —— 一份永远输出 -1 的程序能通过所有合法性检查。 所以判环的结论还得单独对一遍。 （这和第 20 章那句「对拍只能证伪」是同一件事的另一面。）

本章两条出路都用上了：主对拍走出路一（brute vs fast，逐字节比）， 而 dfsTopo.cpp 走出路二 —— check:viz 每轮都拿验证器验它一遍， 再单独核对它的判环结论和 Kahn 一致。

在默认那张图上它输出 1 2 3 4 5 6，一眼就错。可是 ——

如果生成器造 DAG 时只连「编号小 → 编号大」的边（这是最省事的造法， 也几乎是每个人的第一反应），那么数据就白送了一条题目里没有的性质：

编号本身就是一个合法拓扑序，而且正好是字典序最小的那个。

于是这份「什么都不做」的代码 300 轮全对。 一批连「什么都不做」都打不假的数据，你还能指望它验出什么呢？

修法只有一处，而且不改图的形状，只改名字： 先随机一个排列 perm，再连 perm[i] → perm[j]（i < j）。 它立刻从 0 / 300 变成 265 / 300。

这一招和第 27 章「打乱树的点编号」是同一个动作： 别让编号自己带上一层题目没给的含义。

gen.cpp 带了五个档位（./gen 种子 档位）。种子固定 1..300：

档位 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。

每一支都要有，而且都不能多到吃掉别人。 「某一支永远走不到」和「某一支占得太多」，是同一枚硬币的两面。

【1】拓扑排序就是换了入队条件的 BFS。

BFS：       没来过           → 入队
拓扑排序：  所有前驱都出队了  → 入队（记 in[v]，减到 0 就是）

而「依赖谁就先填谁」这句话，从第 21 章一路走到这里，第六次登场 —— 拓扑序就是「依赖顺序」这四个字本身。

【2】判环是白送的：队列空了，出队却不够 n 个。 剩下的人每个都还欠着前驱，顺着「谁欠谁」往回走一定会踩回来 —— 那就是环。 ⚠ 正因为白送，它也最容易被漏掉。

【3】答案不唯一时，先想清楚怎么验，再动手写。 两条出路： 把答案钉唯一（小根堆 + 「字典序最小」），或者写验证器（查排列 + 查每条边前指后）。 ⚠ 验证器的盲区：它证明不了「答案存在时你没漏报」，判环的结论得单独对。

【4】生成器的两头都要看。 既不能让某一支永远走不到（编号就是拓扑序 / 永远无环 → 两个 bug 全是 0 / 300）， 也不能让某一支占得太多（231 轮都有环 → 顺序类的 bug 全被挤没）。 调的时候一次只改一处、每次都实测，而且每一档都留成参数，让读者能整张表重跑。