拓扑排序

拓扑序是有向无环图（DAG）的顶点排列：每条边 u→v 中 u 都在 v 前。存在环时没有拓扑序。

Kahn 算法

先统计所有入度，将入度为 0 的点入队；不断取点加入答案并删除其出边，新的入度 0 点继续入队。最终输出数量小于 n 即表示图有环。

queue<int> q; for(int i=1;i<=n;i++) if(indeg[i]==0) q.push(i);
vector<int> ord;
while(!q.empty()){int u=q.front();q.pop(); ord.push_back(u);
  for(int v:g[u]) if(--indeg[v]==0) q.push(v);
}
if((int)ord.size()!=n) cout<<"cycle";

DFS 方法与应用

DFS 回溯时把点压入序列，最后反转；用 0/1/2 三色标记，遇到正在访问的点可判环。拓扑序常用于课程先修、任务调度、DAG 最短路与 DAG DP；多个入度 0 点的选择不同，合法序不一定唯一。

邻接表实现的时间为 O(n+m)、空间 O(n)。整理自 XOJ《拓扑排序》。