【板子】拓扑排序（少量先后约束，进行合法排列/执行）

一、核心原理1. 它是干什么的解决“先做 A 才能做 B”​ 的问题。把有向无环图 (DAG)​ 拉直成一个序列。保证如果A - BA 依赖 B序列中B 一定在 A 前面注取决于建图逻辑通常我们定义a-b为a做完才能做b即a在前但在“菜肴制作”题中为了“小数靠前”我们采用了反向建图此时y-x意味着x依赖yy在前。2. 为什么要有“无环”如果有环A-B-C-A意味着 A 要在 B 前B 要在 C 前C 要在 A 前。逻辑死锁无解。判环依据拓扑排序输出的节点数 n。3. Kahn 算法BFS底层逻辑入度 (in)​ 有多少人在等你。入度为 0​ 没人等你你现在就可以做。做完一个任务就告诉你的后继“我可以了”入度减 1。当某个后继发现“所有人都搞定了”入度变 0把它加入队列。二、通用算法板子Kahn / BFS这是最常用、最安全的板子适用于 90% 的题。1. 链式前向星存图推荐const int N 1e5 10, M 2e5 10; int h[N], e[M], ne[M], idx; int in[N]; // 入度 void add(int a, int b) { // a-b e[idx] b; ne[idx] h[a]; h[a] idx; } // 初始化 memset(h, -1, sizeof h); idx 0; fill(in, in n 1, 0);2. 拓扑排序主逻辑bool topo(vectorint res) { queueint q; // 1. 把所有入度为0的点入队 for (int i 1; i n; i) { if (in[i] 0) q.push(i); } // 2. BFS while (q.size()) { int u q.front(); q.pop(); res.push_back(u); // 3. 遍历邻接表减少后继的入度 for (int i h[u]; ~i; i ne[i]) { int v e[i]; if (--in[v] 0) { q.push(v); } } } // 4. 判环如果排出的点不够说明有环 return res.size() n; }三、板子的三种“变身”应对不同题型普通情况随便排只要合法特征题目只要求给出一种可行的顺序。板子直接用上面的queueint。字典序最小特征输出时如果多个点可选选编号小的。变身把queue换成priority_queuelessint小根堆。priority_queueint, vectorint, greaterint q;注意这是正向思维谁小谁先出。特殊限制小数尽量靠前洛谷 P3243 菜肴制作特征1 要尽量靠前在保证 1 的前提下 2 要尽量靠前……误区不能用小根堆直接跑。正解反向建图 大根堆 反转结果。// 建图时add(y, x); 原来是 x 依赖 y现在建 y-x // 队列priority_queueint q; // 大根堆 // 输出reverse(res.begin(), res.end());原理与其纠结谁在前不如让大数在后面排队。四、DFS 拓扑排序用于判环或内存受限场景。int st[N]; // 0未访问, 1访问中, 2已结束 vectorint res; bool dfs(int u) { st[u] 1; // 进入递归栈 for (int i h[u]; ~i; i ne[i]) { int v e[i]; if (st[v] 1) return false; // 遇到环 if (st[v] 0 !dfs(v)) return false; } st[u] 2; // 弹出递归栈 res.push_back(u); // 后序插入 return true; } bool topo_dfs() { for (int i 1; i n; i) { if (!st[i] !dfs(i)) return false; } reverse(res.begin(), res.end()); // 必须反转 return true; }五、临场使用决策树考试时按这个顺序想是不是 DAG是 → 拓扑排序否 → 强连通分量Tarjan有没有环有 → 输出Impossible无 → 继续有没有特殊顺序要求无 →queue字典序最小 →priority_queuegreaterint小数尽量前 →反向建图 priority_queuelessintreverse数据多大n 5000→ 链式前向星n 5000→vectorvectorint六、踩坑点坑点症状解决方案多测不清空​WA / TLEh,idx,in必须重置数组开小​REN至少开max(n,m)10下标混淆​WA看清题目是0~n-1还是1~n判环条件​WAres.size() ! nDFS 忘反转​WADFS 拓扑必须reverse