拓扑排序要解决的问题是给一个图的所有节点排序
在一个 DAG（有向无环图） 中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 u 到 v 的有向边 (u,v), 都可以有 u 在 v 的前面。
注:有环的图无法给出拓扑排序 因此也可以用这个性质判断图有无环
int n,m;
int in[N],out[N];//记录入度与出度
int num;
int ans[N];
queue<int> q;
struct node{
int to,w,next;
}e[N];
int head[N];
int cnt;
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
int main()
{
cin>>n>>m;//点 边
for(int i=1;i<=n;i++)head[i]=-1;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
//由u至v
//因此 u出度++ v入度++
in[v]++;
out[u]++;
add(u,out[u],v);
}
for(int i=1;i<=n;i++)
{
if(in[i]==0)
{
//没有先决条件了 可以办掉它
q.push(i);
num++;
ans[num]=i;
}
}
while(!q.empty())
{
int k=q.front();
q.pop();
for(int i=head[k];i!=-1;i=e[i].next)
{
int t=e[i].w;
in[t]--;
if(in[t]==0)
{
q.push(t);
num++;
ans[num]=t;
}
}
}
/*
num用于对特定位置的标识
此处判断是因为--如果可以拓扑排序,那num==n
*/
if(num==n)
{
for(int i=1;i<=num;i++)
cout<<ans[i]<<" ";//拓扑排序输出
}
else
{
cout<<"Error!";
}
return 0;
}