topo排序完全版

 1 #include<stdio.h>
 2 #include<queue>
 3 #include<string.h>
 4 using namespace std;
 5 int indegree[100] ;
 6 queue<int>q;
 7 int n , m ;
 8 bool map[100][100] ;
 9 int a[100] ;
10 int topo(int n)
11 {
12     int cnt = 0 ;
13     while (!q.empty ())
14         q.pop () ;
15 
16     for(int i = 1 ; i <= n ; i++) {
17         if (indegree[i] == 0) {
18             q.push(i);//入度为0的点为起始点
19         }
20     }
21 
22     int temp ;
23     while(!q.empty()) {
24         temp = q.front();
25         a[cnt ++] = temp ;
26         q.pop();
27         for(int i = 1 ; i <= n ; i++) {
28             if(map[temp][i]) {
29                 indegree[i]--;
30                 if(indegree[i] == 0)
31                     q.push(i);
32             }
33         }
34     }
35     if (cnt == n) //当输出的顶点数小于图中的顶点数时，输出有回路信息
36         for (int i = 0 ; i < n ; i++) {
37             printf ("%d----->" , a[i]) ;
38     }
39     else
40         puts ("The network has a cycle!") ;
41 }
42 
43 int main ()
44 {
45    // freopen ("a.txt" , "r" , stdin) ;
46     int u , v ;
47     while (~ scanf ("%d%d" , &n , &m)) {
48         memset (indegree , 0 , sizeof(indegree)) ;
49         memset (map , 0 , sizeof(map)) ;
50         for (int i = 0 ; i < m ; i++) {
51             scanf ("%d%d" , &u , &v) ;
52             if (!map[u][v])//在u 和 v 没有连通时
53                 indegree[v]++ ;//点v的入度++
54             map[u][v] = 1 ;//表示连通
55         }
56         topo (n) ;
57     }
58 }