UVa 10305 Ordering Tasks (例题 6-15)

传送门: https://uva.onlinejudge.org/external/103/10305.pdf

拓扑排序(topological sort)简单题

自己代码的思路来自: ==> http://songlee24.github.io/2015/05/07/topological-sorting/

感谢n久前蔡大神扔给我这个链接2333333

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 111;
 5 bool vis[MAXN];
 6 int G[MAXN][MAXN];
 7 int indegree[MAXN];
 8 int main(){
 9     int n, m;
10     while(cin >> n >> m){
11         if(n == 0 && m == 0) break;
12         memset(vis, false, sizeof(vis));
13         memset(G, 0, sizeof(G));
14         memset(indegree, 0, sizeof(indegree));
15         for(int i = 0; i < m; ++i){
16             int a, b;
17             cin >> a >> b;
18             G[a][b] = 1;
19             indegree[b] += 1;
20         }
21         queue<int> q;
22         while(!q.empty()) q.pop();
23         for(int i = 1; i <= n; ++i)
24             if(!indegree[i]) q.push(i);
25         int total = n;
26         while(!q.empty()){
27             int cur = q.front();
28             q.pop();
29             cout << cur;
30             if(--total) cout << " ";
31             vis[cur] = true;
32             for(int i = 1; i <= n; ++i){
33                 if(G[cur][i]){
34                     --indegree[i];
35                     if(!indegree[i] && !vis[i])
36                         q.push(i);
37                 }
38             }
39         }
40         cout << endl;
41     }
42     return 0;
43 }

入门经典的思路：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 111;
 5 int n, m, t;
 6 int vis[MAXN];
 7 int topo[MAXN];
 8 int G[MAXN][MAXN];
 9 
10 bool dfs(int cur){
11     //vis数组存储三个状态{-1, 0, 1}
12     //-1 代表该点正在访问中(正在栈帧中)
13     // 0 代表该点没有被访问过
14     // 1 代表该点及所有有关系的点都被访问过了
15     vis[cur] = -1;
16     for(int i = 1; i <= n; ++i)
17         if(G[cur][i]){
18             //若在访问中遇到符合要求且正在调用的点,证明图存在有向环,不存在拓扑排序
19             if(vis[i] < 0) return false; 
20             else if(!vis[i] && !dfs(i)) return false;
21         }
22     vis[cur] = 1;
23     topo[--t] = cur;
24     return true;
25 }
26 bool toposort(){
27     t = n;
28     memset(vis, 0, sizeof(vis));
29     memset(topo, 0, sizeof(topo));
30     for(int i = 1; i <= n; ++i)
31         if(!vis[i])
32             if(!dfs(i))
33                 return false;
34     return true;
35 }
36 int main(){
37     while(cin >> n >> m){
38         if(n == 0 && m == 0) break;
39         memset(G, 0, sizeof(G));
40         while(m--){
41             int a, b;
42             cin >> a >> b;
43             G[a][b] = 1;
44         }
45         if(toposort())
46             for(int i = 0; i < n; ++i) cout << topo[i] << " 
"[i == n-1];
47     }
48     return 0;
49 }