拓撲排序

對一個有向無環圖（DAG）進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前；

過程是從入度為0的點開始，放入隊列，然後把該點指向的全部節點的入度減一，如果有頂點的入度變為0了，那麼就放進隊列...

 1 // poj 2367.Genealogical tree
 2 // 拓扑排序
 3 // references:
 4 // no
 5 #include <iostream>
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <algorithm>
 9 #include <vector>
10 #include <queue>
11 
12 using namespace std;
13 
14 const int N = 105;
15 int n;
16 
17 vector <int> v[N];
18 int indegree[N];
19 int ans[N];
20 
21 int main()
22 {
23     while(scanf("%d", &n) != EOF)
24     {
25         int count = 0;
26         memset(v, 0, sizeof(v));
27         memset(indegree, 0, sizeof(indegree));
28         for(int i=1; i<=n; i++)
29         {
30             int m;
31             while(scanf("%d", &m) != EOF && m)
32             {
33                 v[i].push_back(m);
34                 indegree[m]++;
35             }
36         }
37         queue <int> q;
38         for(int i=1; i<=n; i++)
39         {
40             if(indegree[i] == 0)
41                 q.push(i);
42         }
43         while(!q.empty())
44         {
45             int temp = q.front();
46             ans[count++] = temp;
47             q.pop();
48             for(int i=0; i<v[temp].size(); i++)
49             {
50                 if(--indegree[v[temp][i]] == 0)
51                     q.push(v[temp][i]);
52             }
53         }
54         for(int i=0; i<count-1; i++)
55             printf("%d ", ans[i]);
56         printf("%d
", ans[count-1]);
57     }
58     return 0;
59 }