拓扑排序,要让字典序最小,所以把栈改成堆。
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
#define N 100001
priority_queue<int,vector<int>,greater<int> >Q;
int n,m,x,y;
int v[N],first[N],next[N],en,ru[N],tot,ans[N];
void AddEdge(const int &U,const int &V)
{
v[++en]=V;
next[en]=first[U];
first[U]=en;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
ru[y]++;
AddEdge(x,y);
}
for(int i=;i<=n;i++) if(!ru[i]) Q.push(i);
while(!Q.empty())
{
int last=tot;
ans[++tot]=Q.top(); Q.pop();
for(int i=first[ans[tot]];i;i=next[i])
{
ru[v[i]]--;
if(!ru[v[i]]) Q.push(v[i]);
}
}
if(tot!=n) puts("OMG.");
else
{
for(int i=;i<n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
return ;
}