拓撲排序--UVa10305 - acm1314－IT工程師數位筆記本

文章出處

題目

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\n", topo[n-1]+1);
44         }
45         else
46         printf("No\n");
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\n", i, toposort() ? "No" : "Yes");
41 
42     }
43     return 0;
44 }