简介
有向无环图，途中不存在回路。
一个排列，对于有向边 \(u\) 到 \(v\)，那么排列中 \(u\) 一定在 \(v\) 前。
存在拓扑序就不会构成回路。
用队列维护。
点击查看代码
int in[MAXN];//入度
std::queue<int> q;
int ans[MAXN],cnt;
for(int i=1;i<=n;i++)
if(!in[i])q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
ans[++cnt]=x;
for(auto v:g[x])
if(!--in[v])q.push(v);
}
例题 1
求解字典序最小的拓扑序。
每步贪心取出编号最小的点，只需把队列改成小根堆。
例题 2
求一个图的拓扑序是否唯一。