拓扑排序
进阶拓扑排序是 DAG 的线性化，也是很多图论问题的前置步骤。
// 算法讲解
拓扑排序
输入节点数和有向边，观察拓扑排序 Kahn 算法的过程。
待机
速度 中
待机 ⌨1vector<int> topoSort(int V, vector<vector<int>>& adj) {
2 vector<int> indeg(V, 0);
3 for (auto& nb : adj)
4 for (int v : nb) indeg[v]++;
5 queue<int> q;
6 for (int i = 0; i < V; i++)
7 if (indeg[i] == 0) q.push(i);
8 vector<int> order;
9 while (!q.empty()) {
10 int u = q.front(); q.pop();
11 order.push_back(u);
12 for (int v : adj[u])
13 if (--indeg[v] == 0) q.push(v);
14 }
15 return order.size() == V ? order : vector<int>{};
16}
复杂度分析
时间 O(V + E)
空间 O(V)
最优 O(V + E)
最坏 O(V + E)
算法讲解
拓扑排序要求对有向无环图（DAG）的节点排成一个序列，使得每条边 u→v 都满足 u 在 v 之前。
Kahn 算法反复取出入度为 0 的节点并删除其出边，如果最终还有剩余节点则说明有环。
DFS 后序逆序也可以得到拓扑序列，实现更简洁。
它是编译依赖分析、任务调度和很多 DP 问题（如 DAG 上最短路）的基础。