拓撲排序

輸入：一個有向圖

輸出：頂點的拓撲序列

具體流程：

(1) 将所有入度為0的點加入隊列

(2) 每次取出隊首頂點

(3) 删除其連出的邊，檢查是否有新的入度為0的頂點，有則加入隊列

(4) 重複(2)直到隊列為空

樣例輸入

5 5
0 1 1
0 2 1
1 2 1
2 3 1
4 2 1      

樣例輸出

0 4 1 2 3



      

1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 
 5 int ** edges;
 6 int * in_degrees;
 7 int * out_degrees;
 8 int v,e;
 9 
10 void topSort(){
11     queue<int> q;
12     for(int i=0;i<v;i++){
13         if(0 == in_degrees[i]){
14             q.push(i);
15         }
16     }
17     while(!q.empty()){
18         int front = q.front();
19         q.pop();
20         printf("%d ",front);
21         for(int j=0;j<v;j++){
22             if(edges[front][j]!=0){
23                 edges[front][j] = 0;
24                 in_degrees[j]--;
25                 if(0 == in_degrees[j]){
26                     q.push(j);
27                 }
28             }
29         }
30         
31     }
32 }
33 
34 int main(void){
35     cin>>v>>e;
36     //init
37     edges = new int*[v];
38     in_degrees = new int[v];
39     out_degrees = new int[v];
40     memset(in_degrees,0,v*sizeof(int));
41     memset(out_degrees,0,v*sizeof(int));
42     int i;
43     for(i=0;i<v;i++){
44         edges[i] = new int[v];
45         memset(edges[i],0,v*sizeof(int));
46     }
47     
48 
49 
50     //input
51     for(i=0;i<e;i++){
52         int a,b,w;
53         cin>>a>>b>>w;
54         edges[a][b] = w;        //從a到b有一條路
55         in_degrees[b]++;        //b的入度加1
56         out_degrees[a]++;        //a的出度加1
57     }
58 
59     topSort();
60 
61     //huishou
62     for(i=0;i<v;i++){
63         delete edges[i];
64     }
65     delete edges;
66     delete in_degrees;
67     delete out_degrees;
68     return 0;
69 }