图的拓扑序列

 1 #include<cstring>
 2 #include<iostream>
 3 using namespace std;
 4 int n,m;
 5 const int N=1e5+10;
 6 int h[N],e[N],ne[N],idx;
 7 int q[N],d[N];
 8 void add(int a,int b){
 9     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
10 }
11 bool topsort(){
12     int hh=0,tt=-1;
13     for(int i=1;i<=n;i++){
14         if(d[i]==0){
15             q[++tt]=i;
16         }
17     }
18     while(hh<=tt){
19         int t=q[hh++];
20         for(int i=h[t];i!=-1;i=ne[i]){
21             int j=e[i];
22             d[j]--;
23             if(d[j]==0){
24                 q[++tt]=j;
25             }
26         }
27     }
28     return tt==n-1;
29 }
30 int main(void){
31     memset(h,-1,sizeof h);
32     cin>>n>>m;
33     for(int i=0;i<m;i++){
34         int a,b;
35         cin>>a>>b;
36         add(a,b);
37         d[b]++;
38     }
39     if(topsort()){
40         for(int i=0;i<n;i++){
41             cout<<q[i]<<" ";
42         }
43         puts("");
44     }else{
45         puts("-1");
46     }
47     return 0;
48 }

 

上一篇:成语接龙(深搜模板)


下一篇:几大排序算法的理解和代码实现