schindlerlee原創(chuàng)，禁止轉(zhuǎn)載和用于商業(yè)用途
邊看 見(jiàn)過(guò)大爺 邊寫(xiě)竟然5分鐘不到秒了～
拓?fù)渑判蛴袃煞N做法，一種是不斷找入度為0的點(diǎn)，然后刪點(diǎn)和關(guān)聯(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
當(dāng)出現(xiàn)環(huán)時(shí)，找入度為0的方法顯然當(dāng)不能找到入度為0的點(diǎn)時(shí)且還有剩余點(diǎn)則有環(huán)
利用dfs的方法就是找搜索樹(shù)種的回邊，利用染色的方法，算法導(dǎo)論上有介紹
我寫(xiě)的代碼如下：
初始化：memset(vis,0,sizeof(vis));
對(duì)所有vis[i] == 0,調(diào)用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的過(guò)程，建議仔細(xì)體會(huì)一下，求圖的割點(diǎn)，橋，LCA的 tarjen算法主要過(guò)程基本和此dfs過(guò)程非常相似
圖中白色是還未訪(fǎng)問(wèn)的，黑色是已經(jīng)完全訪(fǎng)問(wèn)過(guò)的，藍(lán)色的是正在訪(fǎng)問(wèn)的
