拓扑排序与 DAG 动态规划

一、为什么需要拓扑序？依赖关系的破局之道

在平时的递推和 DP 中，我们习惯了按照数组下标从小到大顺着推：dp[1] -> dp[2] -> dp[3] ...。这种顺序能成功的前提是：小的编号一定是大的编号的前提。

但在现实世界和复杂的竞赛问题中，事物之间的依赖关系很少会乖乖按照编号排好：

• 想穿鞋子（任务 5），必须先穿袜子（任务 3）；
• 想做烤鸭（任务 6），必须先杀鸭（任务 1）、给鸭打气烤制（任务 4）；
• 任务 1 必须在任务 4 之前完成，任务 4 和 3 必须在任务 5 之前完成……

如果我们画出“必须先做 $u$，才能做 $v$”的有向边 $u \to v$，整张任务网就变成了一张有向图。

此时，如果我们还死板地按照节点编号从 $1$ 循环到 $n$，就会遭遇灾难性的“未完工就开工”：假如存在依赖“必须先做任务 $5$，才能做任务 $4$”（即 $5 \to 4$），算到节点 $4$ 时，它的前置任务 $5$ 甚至都还没被碰过！

我们迫切需要一种排序方法：把整张图的节点排成一条线性流水线，使得图里的每一条有向边 $u \to v$，$u$ 都永远排在 $v$ 的前面。

这张严密服从先后依赖的流水线名单，就叫做拓扑序（Topological Order）。

1. 什么是 DAG？为什么“无环”是核心死穴？

能够排出拓扑序的图，必须是 DAG（Directed Acyclic Graph，有向无环图）。

• 可以分叉，也可以汇合：比如两条互不相干的支路分别推进，最后汇聚到一个终点，这完全合法。拓扑序也不一定唯一，谁先谁后只要不违背依赖即可。
• 但绝对不能有环！ 假设出现了环：$1 \to 2 \to 3 \to 1$。
  • $1$ 说：“必须等 $3$ 做完我才能开始。”
  • $3$ 说：“必须等 $2$ 做完我才能开始。”
  • $2$ 说：“必须等 $1$ 做完我才能开始。”

三人互相等待，陷入死锁，没有任何一个人能充当开工的第一个节点。因此：有向图存在拓扑序的充要条件是它是无环图（DAG）。

二、核心算法：Kahn 算法（剥洋葱式入度消除）

怎样在代码里高效排出这张顺序表？最经典的利器是 Kahn 算法，它的本质就像“剥洋葱”：一层层剥掉没有依赖的节点。

1. 灵魂数组：deg[u]（入度）

每个节点的“入度”代表：它当前还有多少个前置任务没有完成。

• deg[u] == 0：表示该节点没有任何前置依赖，或者所有前置任务都已经彻底交工！它是绝对自由的，随时可以开工。
• deg[u] > 0：表示还有债没还清，绝对不能入队，必须继续等待。

2. 算法执行流程

1. 起点甄别：扫描全图，把所有初始入度为 0 的节点统统扔进队列。
2. 流水线推进：从队列中取出一个节点 $u$（这代表任务 $u$ 正式完工，加入拓扑序）。
3. 依赖解绑：遍历 $u$ 的所有出边指向的后继节点 $v$（执行 $u \to v$）：
   • 执行 --deg[v]：后继节点 $v$ 的待办前置任务少了一个！
   • 如果 --deg[v] == 0：说明 $v$ 的最后一笔前置依赖已被彻底结清，此时立即将 $v$ 压入队列！
4. 循环往复，直到队列为空。

3. 手推六点 DAG：紧盯节点 5 的蜕变

我们来看一个极其经典的 6 节点 DAG，包含边：
1 -> 3、2 -> 3、1 -> 4、3 -> 5、4 -> 5、5 -> 6。

每个节点的初始入度为：

• deg[1] = 0, deg[2] = 0
• deg[3] = 2（依赖 1 和 2）
• deg[4] = 1（依赖 1）
• deg[5] = 2（同时依赖 3 和 4）
• deg[6] = 1（依赖 5）

跟踪队列与入度变化：

1. 初始状态：deg[1]=0, deg[2]=0，队列装入 {1, 2}。
2. 处理节点 1：
   • 削减出边后，deg[3] 从 2 降为 1（还不能入队！）；
   • deg[4] 从 1 降为 0，节点 4 满足条件，入队！ 队列变为 {2, 4}。
3. 处理节点 2：
   • 削减出边后，deg[3] 从 1 降为 0，节点 3 满足条件，入队！ 队列变为 {4, 3}。
4. 处理节点 4：
   • 扫描到后继节点 5，执行 --deg[5]，此时 deg[5] 从 2 变成了 1。
   • 此时千万注意：节点 5 虽然等到了节点 4，但节点 3 的工作还没完成，所以 5 绝对不能入队！
5. 处理节点 3：
   • 扫描到后继节点 5，再次执行 --deg[5]，deg[5] 终于从 1 变成了 0！
   • 节点 5 的所有前驱（3 和 4）全部处理完毕，节点 5 正式入队！
6. 处理节点 5：削减出边，deg[6] 降为 0，节点 6 入队。
7. 处理节点 6：结束。

最终生成的一组合法拓扑序为：1, 2, 4, 3, 5, 6。

💡 核心警示：
节点 5 必须等待来自 4 和 3 的两记扣减，经历 2 -> 1 -> 0 的蜕变后才能进队。千万不能看到一条入边被处理就贸然把终点塞进队列！

4. 判环的试金石：队列空了，是成功还是卡死？

当 q.empty() 时，一定意味着排序成功了吗？不一定！

我们用一个计数器 cnt 记录总共从队列中弹出了多少个节点：

• 如果 cnt == n：说明所有点都顺利走完了依赖消除，原图是纯正的 DAG。
• 如果 cnt < n：说明原图中必定存在环！环上的节点因为互相牵制，入度永远不可能降到 0，连同被环卡死的所有后代节点一起，永远无法入队。

// 核心片段：Kahn 算法与拓扑序提取
queue<int> q;
for(int i=1;i<=n;i++){
	if(deg[i]==0) q.push(i);
}

vector<int> ord;
while(!q.empty()){
	int u=q.front();
	q.pop();
	ord.push_back(u);
	
	for(int i=0;i<node[u].size();i++){
		int v=node[u][i];
		if(--deg[v]==0) q.push(v);
	}
}

// 如果弹出的点不足 n 个，说明图中有环！
if(ord.size()<n){
	// 存在环的异常处理
}

三、拓扑序的降维打击：让 DAG 上的动态规划如履平地

很多同学做一般图上的最短路、最长路或路径计数，第一反应是写 SPFA 或 Dijkstra，甚至乱搜一气。

但在 DAG 上，那些复杂的图论松弛算法通通是“大炮打蚊子”。因为 DAG 天生自带一种至高无上的性质——无后效性！

1. 为什么普通图不能直接递推，而 DAG 可以？

在有环的图上，$u$ 影响 $v$，$v$ 绕一圈又会反过来影响 $u$，状态相互纠缠，无法按线性顺序计算。

但在 DAG 上，只要我们沿着拓扑序从前往后推进：

当节点 $u$ 从队列弹出时，所有能够到达 $u$ 的前驱节点，已经在之前全部被处理完毕了！

这就像工地上盖楼：地基（入度为 0）打好了，才浇筑一层；一层彻底凝固硬化了，才浇筑二层……当工人被通知去盖二层时，一层的质量参数和尺寸已经彻底定型，绝对不可能再发生任何变动！

因此，我们不需要任何回溯，直接在拓扑排序出队的同时顺手转移 DP：

• 求路径方案数：各前驱方案累加，dp[v] = (dp[v] + dp[u]) % MOD；
• 求最长路径：各前驱最优值取最大，dp[v] = max(dp[v], dp[u] + w)；
• 求最短路径：各前驱最优值取最小，dp[v] = min(dp[v], dp[u] + w)。

时间复杂度仅为极速的 $O(N + M)$，每条边恰好转移一次！

四、完整程序一：P4017 最大食物链计数

💡 【实战例题 1】洛谷 P4017 最大食物链计数

【问题描述】
给你一张食物网（保证为 DAG），包含 $n$ 种生物和 $m$ 条捕食关系。若生物 $A$ 被生物 $B$ 吃，则连一条有向边 $A \to B$。
处于食物链顶端的是“没有任何捕食者”的最终消费者（出度为 0）；处于底端的是“不捕食任何其他生物”的生产者（入度为 0）。
现要求计算：图中共有多少条完整的最大食物链？答案对 $80112002$ 取模。

【输入格式】
第一行两个整数 $n, m$。
接下来 $m$ 行，每行两个整数 $A, B$，表示 $A$ 被 $B$ 吃（即边 $A \to B$）。

【输出格式】
一个整数，表示最大食物链的总数对 $80112002$ 取模后的值。

【数据范围】
$1 \le n \le 5000$，$1 \le m \le 500000$。

1. 破题盲区与物理意义

千万不要望文生义把“最大食物链”当成“长度最长（节点最多）的链”！

• 题目的定义是：从任意一个生产者（入度为 0）出发，走到任意一个最终消费者（出度为 0）的路径，无论长短，都算一条完整的食物链。
• 即使有一条链长只有 1（比如 $1 \to 6$ 直达），只要 1 入度为 0 且 6 出度为 0，它就是一条合法的食物链！

2. 状态设计与转移

• 状态定义：设 f[u] 表示从所有合法的起点出发，到达节点 $u$ 的路径总数。
• 初值设定：对于所有初始入度为 0 的生产者，f[u] = 1（自己作为一个起点，有 1 种初始方案）。其余点均为 0。
• 状态转移：在拓扑排序中，取出 $u$ 后，遍历出边 $u \to v$：
  $$f[v] = (f[v] + f[u]) \bmod 80112002$$
• 终局汇总：最后答案是把所有出度为 0 的节点的 f[u] 累加起来。切记不能累加出度不为 0 的中间节点，否则会把未完工的半截链算进去！

3. 完整标程实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
const int MOD=80112002;

vector<int> node[N];
int deg[N],out[N],f[N];
int n,m;

void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		node[u].push_back(v);
		deg[v]++; // 统计入度
		out[u]++; // 统计出度，用来锁死最终消费者
	}
	
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(deg[i]==0){
			f[i]=1;     // 生产者初始方案数为 1
			q.push(i);
		}
	}
	
	int cnt=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		cnt++;
		
		for(int i=0;i<node[u].size();i++){
			int v=node[u][i];
			f[v]=(f[v]+f[u])%MOD; // 沿拓扑序下发方案数
			if(--deg[v]==0){
				q.push(v);
			}
		}
	}
	
	if(cnt!=n){
		cout<<-1<<'\n'; // 存在环，约定输出-1（原题保证DAG不会触发此分支）
		return;
	}
	
	// 汇总所有最终消费者（出度为 0）的方案
	int ans=0;
	for(int i=1;i<=n;i++){
		if(out[i]==0){
			ans=(ans+f[i])%MOD;
		}
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

五、完整程序二：P1807 最长路

💡 【实战例题 2】洛谷 P1807 最长路

【问题描述】
给出一个包含 $n$ 个点、$m$ 条有向边的带权 DAG。求从节点 $1$ 到节点 $n$ 的最长路径长度。若从 $1$ 出发无法到达 $n$，则输出 -1。注意：边权可能为负数。

【输入格式】
第一行两个整数 $n, m$。
接下来 $m$ 行，每行三个整数 $u, v, w$，表示一条从 $u$ 到 $v$ 权值为 $w$ 的有向边。

【输出格式】
一个整数，表示从 $1$ 到 $n$ 的最长路径长度；若无法到达输出 -1。

【数据范围】
$1 \le n \le 1500$，$1 \le m \le 50000$，$-10^5 \le w \le 10^5$。

1. 为什么 Dijkstra 做不了，而 DAG 拓扑 DP 毫无压力？

普通图求最长路是 NP-Hard 问题，而且如果存在正环，最长路甚至可以无限大。

但本题是 DAG（无环图）！没有环，就绝对不可能发生无限绕圈。即便是负权边，也丝毫不会破坏拓扑序的前后依赖逻辑。

2. 避坑三连斩：考场失分的高频重灾区

坑点一：初值千万不能初始化为 0！

如果全图初始化为 0：

1. 若图中有负权边（比如 $1 \to 2$ 权值是 $-4$），如果 f[2] 初始为 0，转移时取 $\max(0, 0 + (-4)) = 0$，负代价会被直接吞掉！
2. 如果存在某些节点根本无法从 $1$ 到达（比如点 $3 \to 4$ 权值是 $100$），如果点 3 初始设为 0，程序就会误以为能从 3 凭空出发，用 $0 + 100$ 错误更新点 4！

• 物理准则：除了 f[1] = 0，其他所有点全部置为极小值（负无穷 -INF），代表目前绝对不可达！

坑点二：初始队列必须加入“全图所有入度为 0 的点”，绝不能只放节点 1！

很多初学者以为“只求 1 到 $n$ 的最长路，那队列只塞 1 号点不就行了？”——大错特错！

假设节点 4 依赖节点 1 和无关节点 3（$1 \to 4, 3 \to 4$）。如果你的队列只放 1，节点 3 永远没有机会出队，那么节点 4 的入度就永远只能减到 1，导致节点 4 及其所有下游节点（包括终点 $n$）彻底被卡死在队列之外！

• 物理准则：
  • 拓扑解耦属于全图：所有入度为 0 的节点必须统统进队列，正常剥洋葱消入度；
  • DP 状态属于合法路径：只有当 f[u] != -INF 时，才允许用它的权值去松弛后继 f[v] = max(f[v], f[u] + w)！

坑点三：不可达的终局判断不能写成 f[n] < 0！

因为边权可能是负数，从 1 到 $n$ 哪怕全由负权边组成，算出来的最长路完全可能是 $-1, -2, -50$。 如果把结果小于 0 就判定为不可达，会当场 WA 掉所有合法负权路径。

• 物理准则：只有 f[n] == -INF 时，才代表真的走不到，此时输出 -1；否则直接输出 f[n]。

3. 完整标程实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
const int INF=1e18;

struct Edge{
	int v,w;
};

vector<Edge> node[N];
int deg[N],f[N];
int n,m;

void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		node[u].push_back({v,w});
		deg[v]++;
	}
	
	// 1. 除了起点 1，其余全部标记为负无穷（不可达）
	for(int i=1;i<=n;i++) f[i]=-INF;
	f[1]=0;
	
	// 2. 所有 0 入度点全部入队，保证整图拓扑推进不卡死
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(deg[i]==0) q.push(i);
	}
	
	int cnt=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		cnt++;
		
		for(int i=0;i<node[u].size();i++){
			int v=node[u][i].v;
			int w=node[u][i].w;
			
			// 只有当前驱 u 真实可达时，才允许转移收益
			if(f[u]!=-INF){
				f[v]=max(f[v],f[u]+w);
			}
			
			// 无论 u 是否可达，度数必须正常削减
			if(--deg[v]==0){
				q.push(v);
			}
		}
	}
	
	if(cnt!=n){
		cout<<-1<<'\n'; // 存在环，约定输出-1（原题保证DAG不会触发此分支）
		return;
	}
	
	// 3. 严格比对是否仍为负无穷，不能用 f[n]<0 瞎猜
	if(f[n]==-INF) cout<<-1<<'\n';
	else cout<<f[n]<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

六、拓扑 DP 的通关心法与调试技巧

写完拓扑 DP，怎样在考场上用最小代价抓出 Bug？记住下面 4 张经典自测手推小图：

1. 单向直链测试：
   1 -> 2 -> 3 -> 4。检查答案是否能像多米诺骨牌一样顺滑推到末尾。
2. 经典菱形测试：
   1 -> 2 -> 4，1 -> 3 -> 4。检查汇聚点 4 是否正确汇总了分支 2 和分支 3 的贡献（是相加还是取最大）。
3. 独立悬空分支测试：
   除了 $1 \to 2$，旁边独立悬挂一条 $3 \to 4$（权值极大）。检查 3 和 4 是否正确进队消度，同时验证 3 和 4 的非法收益没有污染主分支的答案。
4. 环与死锁保护测试：
   构造一条小环 $2 \to 3 \to 2$。检查程序是否能通过 cnt != n 警惕出环的存在，而不是死循环或产生越界。

七、拓扑序的唯一性与字典序最小

1. 如何判断拓扑序是否唯一？

在执行 Kahn 算法时，我们的队列就像一个“待办任务等候室”。

如果在运行的任意时刻，队列里的元素个数大于 1，这意味着当前有多个节点同时满足了“前置任务全清”的条件，它们谁先出队都是合法的。 换句话说，在确认整张图是 DAG 的前提下，只要队列长度曾超过 1，拓扑序就不是唯一的；反之，如果队列长度始终保持 $\le 1$，那整条流水线就是一条绝对单行道，拓扑序唯一。

回看第二节第 3 小节的六点例子：1, 2, 4, 3, 5, 6 与 1, 2, 3, 4, 5, 6 都是合法拓扑序，开局队列里就同时有 1、2 两个候选点。

2. 字典序最小的拓扑序

当拓扑序不唯一时，题目常常要求输出“字典序最小”的拓扑序：比较两个序列时，找到第一个不同的位置，该位置编号更小的序列更优。这和“先让 1 尽量靠前，再让 2 尽量靠前……”不是同一种要求。 既然队列里同时存在多个合法的候选人，我们只需要把普通的 queue 换成优先队列（小根堆）。每次需要派人出队时，小根堆会自动把当前等候室里编号最小的节点推到最前面。

代码变更片段：

// 普通队列：queue<int> q;
// 替换为小根堆（优先队列）：
priority_queue<int, vector<int>, greater<int>> pq;

// 入队操作不变
pq.push(i);

// 出队操作变为 top() 和 pop()
int u = pq.top();
pq.pop();

💡 避坑：小根堆只能保证“每次拿出的可行点编号最小”，也就是正向贪心。如果是像《菜肴制作》那种“让编号小的尽可能靠前（优先照顾小编号）”的限制，直接正向贪心是错的，需要建反图后用大根堆跑拓扑序，最后将结果逆序。

八、顺藤摸瓜：如何在 DP 中恢复最长路路径

前面的最长路模板只算出了“最长能走多远”，但如果题目要求把这条最长路的具体经过了哪些点打印出来呢？

状态转移时我们做的是 f[v] = max(f[v], f[u] + w)。为了知道 v 的分数是从哪来的，我们只需要在 v 成功被 u 更新时，额外找个本子记下来：“v 的上一站是 u”。这个本子就是前驱数组 pre。

关键转移片段：

if(f[u] != -INF && f[u] + w > f[v]) {
    f[v] = f[u] + w;
    pre[v] = u;  // 成功松弛，记录前驱
}

路径恢复片段： 当拓扑 DP 结束后，假设走到终点 n 取得了最大值，我们就可以从 n 开始顺藤摸瓜往回找，直到退回起点。

vector<int> path;
int curr = n;
while(curr != 0) {       // 假设起点 1 的 pre[1] 初始化为 0
    path.push_back(curr);
    curr = pre[curr];
}

// 因为是从终点往回找的，路径是反的，输出前必须翻转
reverse(path.begin(), path.end());

for(int i=0; i<path.size(); i++){
    cout << path[i] << (i == path.size()-1 ? "" : "->");
}

九、DAG 可达性统计与 bitset 压位优化（选学）

先修要求：了解基本的位运算（与、或、非）；不熟悉压位操作时，可先看《bitset：批量状态转移与常数优化》。

场景：给定一个 DAG，对于每一个节点，它能顺着有向边走向多少个不同的节点？

这个问题的难点在于去重。假设存在边 $A \to B, A \to C, B \to D, C \to D$，那么 $A$ 走到 $D$ 有两条路。如果单纯用普通的加法累加可达点数量，$D$ 会被算两次！

1. 集合求并与逆向拓扑序

为了去重，节点 $u$ 的可达点集合，应该等于它所有出边指向的后继节点 $v$ 的可达点集合的“并集”，再加上 $u$ 自己。

既然 $u$ 需要拿它后继节点的结果来合并，这就意味着：处理 $u$ 的时候，它的后继节点 $v$ 必须已经算完绝对定型了。 所以，我们不能顺着拓扑序推进，而是要逆着拓扑序倒着推！

2. bitset 压位优化

如果用 vector 存储集合再去重合并，速度极慢。C++ 提供了神器 std::bitset，它相当于一个极度压缩的布尔数组。每个点用 1 个 bit 表示可达状态，30000 个点只需要大约 3.7 KB。 合并集合的操作，直接退化成了一步极速的二进制“按位或”：f[u] |= f[v]。

3. 完整程序实现

下面这份程序展示了如何利用 Kahn 算法排出的序列进行逆向遍历。这比大费周章地去建立一张有向图的反图要优雅得多。

// 自拟练习：DAG 可达性统计
// 【输入格式】
// 第一行 n, m (1 <= n, m <= 30000)
// 接下来 m 行，每行两个整数 u, v，表示单向边 u -> v
// 【输出格式】
// 输出 n 行，第 i 行表示节点 i 能到达的节点总数（包含自身）
/*
样例输入：
4 4
1 2
1 3
2 4
3 4

样例输出：
4
2
2
1
*/

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 30005;

vector<int> node[N];
int deg[N];

// f[u] 的第 i 位为 1，表示节点 u 可以到达节点 i
// 30005 * 30005 bit 约 107 MiB，提交前先看内存限制
bitset<N> f[N]; 

void solve(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		node[u].push_back(v);
		deg[v]++;
	}
	
	// 初始化：每个点肯定能到达自己
	for(int i = 1; i <= n; i++){
		f[i][i] = 1;
	}
	
	// Kahn 算法求正常拓扑序
	queue<int> q;
	for(int i = 1; i <= n; i++){
		if(deg[i] == 0) q.push(i);
	}
	
	vector<int> ord;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		ord.push_back(u);
		
		for(int i = 0; i < node[u].size(); i++){
			int v = node[u][i];
			if(--deg[v] == 0) q.push(v);
		}
	}
	
	// 核心：逆着拓扑序倒推（自底向上合并集合）
	// ord 数组里存放的是正向拓扑序，逆序遍历它
	for(int i = n - 1; i >= 0; i--){
		int u = ord[i];
		// 遍历 u 的所有后继节点 v
		for(int j = 0; j < node[u].size(); j++){
			int v = node[u][j];
			// u 的可达集合并上 v 的可达集合
			f[u] |= f[v];
		}
	}
	
	// count() 函数直接返回 bitset 中 1 的个数
	for(int i = 1; i <= n; i++){
		cout << f[i].count() << '\n';
	}
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

十、渐进式实战练习题单

第一阶段：肌肉记忆与拓扑基石

1. 洛谷 B3644 【模板】拓扑排序 / 家谱树
   • 训练指引：纯粹的拓扑排序板子题。建立 deg 数组，掌握队列消除入度的基本功。
2. 洛谷 P1113 杂务
   • 训练指引：每个任务必须等所有前置任务完成，耗时取所有前驱的最大值加上自身耗时。最纯粹的 DAG 最长路入门。

第二阶段：图上 DP 融合突破

3. 洛谷 P4017 最大食物链计数
   • 训练指引：反复体会本篇例题 1，抓准“入度为 0 赋初值，出度为 0 累加统计”的边界规范。
4. 洛谷 P1807 最长路
   • 训练指引：彻底搞懂不可达点 -INF 初始化与负权边转移逻辑，做到不看题解一次写对。

第三阶段：综合变种与反向思维

5. 洛谷 P1983 [NOIP2013 普及组] 车站分级
   • 训练指引：模型转化神题。停靠的车站等级一定严格大于没停靠的车站，把大小关系转化为有向边拓扑分层。
6. 洛谷 P3243 [HNOI2015] 菜肴制作
   • 训练指引：要求“让编号小的尽量靠前”。千万不能贪心用小根堆跑正向拓扑排序！需要反向建图 + 大根堆跑拓扑序再逆序输出，是考察拓扑序数学本质的省选经典。