首页 > 代码库 > POJ1094 拓扑排序

POJ1094 拓扑排序

2024-07-10 15:10:10   220人阅读

问题：POJ1094
 
本题考查拓扑排序算法
 
拓扑排序：
 
1）找到入度为0的点，加入已排序列表末尾；
2）删除该点，更新入度数组。
 
循环1）2）直到
1. 所有点都被删除，则找到一个拓扑排序；
2. 或剩余结点中没有入度为0的点，则原图中必存在环。
 
 
本题算法
 
1.依次输入一组关系
 
对当前关系进行拓扑排序
1）若存在环，则无法排序
2）若根据当前关系，每次循环都唯一的确定入度为0的点，则存在排序
 
2.若输完所有的大小关系之后，仍然没有确定大小排序，也没有发现回环，则排序无法唯一确定
 
AC代码：
 1 //Memory: 224K        Time: 0MS 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <string> 6  7 using namespace std; 8  9 const int maxn = 26;10 bool g[maxn][maxn];11 int indegree[maxn];12 int in[maxn];13 int vis[maxn];14 int flag;15 int n, m;16 int out[maxn];17 string s;18 int size;19 int ans;20 21 int topologicalSort()22 {23     memset(vis, 0, sizeof(vis));24     memcpy(in, indegree, sizeof(in));25     size = 0;26     flag = 0;27     while (size < n){28         int num = 0;29         int next;30         for (int i = 0; i < n; i++){31             if (vis[i]) continue;32             if (in[i] == 0) {33                 num++;34                 if (num > 1) break;35                 next = i;36             }37         }38         if (num == 0) return 0;39         else {40             out[size++] = next;41             vis[next] = 1;42             for (int i = 0; i < n; i++) {43                 if ( g[next][i] && !vis[i] )44                     in[i]--;45             }46             if (num > 1)47                 flag = 1;48         }49     }50     if (flag == 0) return 1;51     else return 2;52 }53 54 int main()55 {56     while (cin >> n >> m && n) {57         memset(g, 0, sizeof(g));58         memset(indegree, 0, sizeof(indegree));59         ans = 2;60         for (int i = 0; i < m; i++){61             cin >> s;62             if ( ans != 2 ) continue;63             if (!g[s[0] - ‘A‘][s[2] - ‘A‘]) {64                 g[s[0] - ‘A‘][s[2] - ‘A‘] = 1;65                 indegree[s[2] - ‘A‘]++;66                 ans = topologicalSort();67 68                 if (ans == 0) {69                     cout << "Inconsistency found after " << i + 1 <<" relations." << endl;70                 }71                 else if ( ans == 1 ){72                     cout << "Sorted sequence determined after " << i + 1 << " relations: ";73                     for (int i = 0; i < n; i++)74                         cout << (char)(out[i] + ‘A‘);75                     cout << "." << endl;76                 }77             }78         }79         80         if ( ans == 2 )81             cout << "Sorted sequence cannot be determined." << endl;82     }83     return 0;84 }

 


联系
我们