schindlerlee原創(chuàng)，禁止轉載和用于商業(yè)用途
邊看 見過大爺 邊寫竟然5分鐘不到秒了～
拓撲排序有兩種做法，一種是不斷找入度為0的點，然后刪點和關聯(lián)的邊，一種是利用dfs退棧的順序
如下：
1 /*
2 * SOUR:pku 2367
3 * ALGO:top sort
4 * DATE: Mon, 12 Oct 2009 00:56:07 +0800
5 * COMM:2
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 #include<vector>
13 using namespace std;
14 typedef long long LL;
15 const int maxint = 0x7fffffff;
16 const long long max64 = 0x7fffffffffffffffll;
17 #define pr(x
) fprintf(stderr, x)
18 /* #define pr(x) for(;0;) */
19 const int N = 128;
20 vector < int >g[N];
21 int dfn[N], n, vis[N], st[N], top;
22
23 void dfs(int u)
24 {
25 if (vis[u]) return;
26 vis[u] = true;
27 for (int i = 0; i < g[u].size(); i++) {
28 dfs(g[u][i]);
29 }
30 st[top++] = u;
31 }
32
33 int main()
34 {
35 int i, j, k, u, v;
36 scanf("%d", &n);
37 for (u = 1; u <= n; u++) {
38 while (1) {
39 scanf("%d", &v);
40 if (0 == v)
41 break;
42 g[u].push_back(v);
43 }
44 }
45 for (u = 1; u <= n; u++) {
46 if (!vis[u]) {
47 dfs(u);
48 }
49 }
50 for (i = top - 1; i > 0; i--) {
51 printf("%d ", st[i]);
52 }
53 printf("%d\n", st[i]);
54 return 0;
55 }
56
當出現(xiàn)環(huán)時，找入度為0的方法顯然當不能找到入度為0的點時且還有剩余點則有環(huán)
利用dfs的方法就是找搜索樹種的回邊，利用染色的方法，算法導論上有介紹
我寫的代碼如下：
初始化：memset(vis,0,sizeof(vis));
對所有vis[i] == 0,調用dfs
bool dfs(int u)
{
if(vis[u] == 1) return false;
if(vis[u] == 2) return true;
vis[u] = 1;
for(i = 0;i < g[u].size();i++) {
if(false == dfs(g[u][i])) {
return false;
}
}
vis[u] = 2;
stack[top++] = u;
return true;
}
下圖描述了dfs的過程，建議仔細體會一下，求圖的割點，橋，LCA的 tarjen算法主要過程基本和此dfs過程非常相似
圖中白色是還未訪問的，黑色是已經完全訪問過的，藍色的是正在訪問的
