拓扑排序

输入：一个有向图

输出：顶点的拓扑序列

具体流程：

(1) 将所有入度为0的点加入队列

(2) 每次取出队首顶点

(3) 删除其连出的边，检查是否有新的入度为0的顶点，有则加入队列

(4) 重复(2)直到队列为空

样例输入

样例输出

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 }