智能网站开发工具建网站模板

又重新学了一下拓扑排序，这次发现就十分简单了，拓扑排序的步骤

1.他必须是一个有向无环图，起点我们就是入度为0的点

2.我们首先要输出的就是入度为0的点，然后依次删除这些点连向的点，使这些点的入度-1，如果这些点入度此时变为了0，那么就放进刚才入度为0的集合当中

3.现在只需要输出这个集合就可以了

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=100010;
int e[N];
int ne[N];
int h[N];
int idx=0;
int hh=0,tt=-1;
int q[N];
int d[N]; 
void add1(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort()
{for(int i=1;i<=n;i++){if(d[i]==0)q[++tt]=i;}while(tt>=hh){int j=q[hh++];for(int i=h[j];i!=-1;i=ne[i]){int x=e[i];d[e[i]]--;if(d[e[i]]==0){q[++tt]=e[i];}}}if(tt==n-1){for(int i=0;i<n;i++){cout<<q[i]<<" ";}}else{cout<<"-1";}
}
int main()
{cin>>n>>m;memset(h,-1,sizeof(h));while(m--){int a,b;cin>>a>>b;d[b]++;add1(a,b);}topsort();return 0;
}