拓扑排序--UVa10305

题目

Output: standard output

Time Limit: 1 second

Memory Limit: 32 MB

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

Input

The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 <= n <= 100 and m. n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j. An instance with n = m = 0 will finish the input.

Output

For each instance, print a line with n integers representing the tasks in a possible order of execution.

Sample Input

5 4

1 2

2 3

1 3

1 5

0 0

Sample Output

1 4 2 5 3

（不好意思， 忘了这道题目啦， 现在给出思路和题解吧！） 其实这个问题就是裸裸的拓扑排序， 首先解释一下什么是拓扑排序？ 就是有些事， 而你要完成这件事前， 就必须要完成另一件事。 就像你
如果想要一个孩子， 就必须要先有个女票一样（结不结婚不是问题， 呵呵！）。  而要有女票， 你就要先谈场恋爱， ，，，，好啦！ 这下拓扑排序解释清楚啦！ 重要性也显现出来啦！ 它可是能关系
到终身大事的算法啊！（嘿嘿！）。      
　　排序方法： 把每个变量看成一个点， “小于”关系看成有向边， 则得到一个有向图。 这样， 我们实际上只需把这个图的所有节点排序。 使得每一条有向边（u，v）对应的u都在v的前面。 在图论中
这个问题称为拓扑排序。
很明显， 若在图中存在有向环， 则不存在拓扑排序。  可以借助DFS完成拓扑排序。 在访问完一个结点以后把它加到当前拓扑序的尾部。 （聪明的你想一下， 为什么不是首部）。 机智的我告诉你，试想
最后一件事， 一定是在最后做的， 然后向前滚， （刚好是DFS的逆序， 哈哈！ 太巧妙啦）。

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn = 1000;
 4 
 5 int n, m, G[maxn][maxn], c[maxn], topo[maxn], t;
 6 
 7 bool dfs(int u)
 8 {
 9     c[u] = -1; //标记一下， 表示正在访问 
10     for(int v=0; v<n; v++) if(G[u][v])
11     {
12         if(c[v]<0) return false;//存在有向环。 
13         else if(!c[v]) dfs(v);
14     }
15     c[u] = 1; topo[--t] = u;//DFS向根追溯。  
16     return true;
17 }
18 
19 bool toposort()
20 {
21     t=n; 
22     memset(c, 0, sizeof(c));
23     for(int u=0; u<n; u++) if(!c[u])
24     if(!dfs(u)) return false;
25     return true;
26 }
27 
28 int main()
29 {
30     while(scanf("%d%d", &n, &m)==2&&n)
31     {
32         memset(G, 0, sizeof(G));//标记有向线段。 
33         for(int i=0; i<m; i++)
34         {
35             int u, v;
36             scanf("%d%d", &u, &v); u--; v--;
37             G[u][v] = 1;
38         }
39         if(toposort())
40         {
41             for(int i=0; i<n-1; i++)
42             printf("%d ", topo[i]+1);
43             printf("%d
", topo[n-1]+1);
44         }
45         else
46         printf("No
");
47     }
48     return 0;
49 }
50 
51 //代码解释： c[u]=0表示从没访问过，c[u] = 1 表示已经访问过啦。
52 //c[u] = -1表示正在访问（即递归调用dfs（u）正在栈桢中， 尚未返回）。

View Code

《2》来道模板题吧！（其实还是有一点要注意的，嘿嘿！）。
http://acm.hdu.edu.cn/showproblem.php?pid=4324

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int maxn = 2000+5;
 7 
 8 int n,  c[maxn];
 9 char G[maxn][maxn];
10 
11 bool dfs(int u)
12 {
13     c[u] = -1;
14     for(int v=0; v<n; v++)
15     if(G[u][v]=='1')
16     {
17         if(c[v]<0) return false;//有环 
18         else if(!c[v]&&!dfs(v)) return false;//有环，这一点注意 
19     }
20     c[u] = 1;
21     return true;
22 }
23 
24 bool toposort()
25 {
26     memset(c, 0, sizeof(c));
27     for(int u=0; u<n; u++)if(!c[u])
28     if(!dfs(u)) return false;
29     return true;
30 }
31 int main()
32 {
33     int T;
34     scanf("%d", &T);
35     for(int i=1; i<=T; i++)
36     {
37         scanf("%d", &n);
38         for(int j = 0; j<n; j++)
39         scanf("%s", G[j]);
40         printf("Case #%d: %s
", i, toposort() ? "No" : "Yes");
41 
42     }
43     return 0;
44 }

View Code

有疑问，请细读代码， DFS递归真的很，，，（哈哈！）。