拓扑排序

介绍见链接：http://baike.baidu.com/link?url=hA4jA5BlgtJd4ktn_bhjpR8ebKR6N7MYAP7L4oe5H8PL3sJr0XhI8hjpXd4IRw263LBm2vpUtbLFT3NQoSeava

原理讲解见这篇文章：http://blog.csdn.net/dm_vincent/article/details/7714519

实现有两种方法：

一种是从入度出发，代码如下：

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 vector<pair<int,int> > eg[100];
 7 
 8 typedef pair<int,int> pa;
 9 
10 //拓扑排序
11 void topo(int n,int d)
12 {
13           queue<int> setOfZeroIndegree;
14           int degrees[100];
15           queue<int> result;
16 
17           //init
18           for(int i = 0;i<n;i++)
19                     degrees[i] = 0;
20 
21           //得到每个顶点的入度
22           for(int i = 0;i<n;i++)
23           {
24                     for(int j = 0;j<eg[i].size();j++)
25                     {
26                               pa x = eg[i][j];
27                               degrees[x.first]++;
28                     }
29           }
30 
31           for(int i = 0;i<n;i++)
32                     if(degrees[i]==0)
33                               setOfZeroIndegree.push(i);
34           int edge = n;
35           while(!setOfZeroIndegree.empty())
36           {
37                     int s = setOfZeroIndegree.front();
38                     setOfZeroIndegree.pop();
39                     result.push(s);
40                     for(int i = 0;i<eg[s].size();i++)
41                     {
42                               pa x = eg[s][i];
43                               degrees[x.first]--;
44                               edge--;
45                               if(degrees[x.first]==0)
46                                         setOfZeroIndegree.push(x.first);
47                     }
48           }
49 
50           if(edge!=0)
51           {
52                     cout<<"There is a circle!
";
53                     return;
54           }
55 
56           while(!result.empty())
57           {
58                     int p = result.front();
59                     result.pop();
60                     cout<<p<<"->";
61           }
62           cout<<endl;
63 
64 
65 
66 
67 };
68 
69 
70 int main()
71 {
72           int n,d;
73           cin>>n>>d;
74           for(int i = 0;i<d;i++)
75           {
76                     int t,s,w;
77                     cin>>t>>s>>w;
78                     eg[t].push_back(make_pair(s,w));
79           }
80           topo(n,d);
81 
82 
83 
84 }
85 /*
86 6 8
87 0 1 2
88 0 3 4
89 1 4 4
90 2 0 5
91 2 5 2
92 3 4 3
93 3 5 7
94 5 4 3
95 */

还有一种是从出度入手，和DFS非常类似，见DFS算法