schindlerlee原创，禁止转载和用于商业用途
边看 见过大爷 边写竟然5分钟不到秒了～
拓扑排序有两种做法，一种是不断找入度为0的点，然后删点和关联的边，一种是利用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
当出现环时，找入度为0的方法显然当不能找到入度为0的点时且还有剩余点则有环
利用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过程非常相似
图中白色是还未访问的，黑色是已经完全访问过的，蓝色的是正在访问的
