首页 > 代码库 > POJ 1094 Sorting It All Out
POJ 1094 Sorting It All Out
http://poj.org/problem?id=1094
题意：
给出n个大写字母和m个关系式，判断是否有序排列并求出排列顺序。
思路：
拓扑排序。根据题意的话每读一个关系式都需要进行拓扑排序，检验由此是否可以求出排列顺序或者判断出是否有环。
关于拓扑排序：
每次寻找入度为0的点，从该点出发，删掉有该点有关的边并使与该点相连的点的入度-1，重复上述步骤，直至把所有点都挑出来。如果中国有环的话，那么到时候肯定就没有入度为0的点了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 8 const int maxn = 30; 9 10 int n, m;11 int g[maxn][maxn];12 int indegree[maxn];13 int ans[maxn];14 15 int tuopu()16 {17 int temp[maxn];18 int flag = 1;19 memcpy(temp, indegree, sizeof(indegree));20 int cnt = 0;21 22 for (int i = 0; i < n; i++)23 {24 int num = 0, loc;25 for (int j = 0; j < n; j++)26 {27 if (temp[j] == 0)28 {29 num++;30 loc = j;31 }32 }33 if (num == 0) return 0; //没有入度为0的点，说明有环34 if (num>1) flag=-1;35 ans[cnt++] = loc;36 temp[loc] = -1;37 for (int j = 0; j < n;j++)38 if (g[loc][j]) temp[j]--;39 }40 return flag;41 }42 43 int main()44 {45 //freopen("D:\\txt.txt", "r", stdin);46 char s[5];47 while (~scanf("%d%d", &n, &m))48 {49 if (m == 0 && n == 0) break;50 memset(g, 0, sizeof(g));51 memset(indegree, 0, sizeof(indegree));52 memset(ans, 0, sizeof(ans));53 int flag = 0;54 for (int i = 1; i <= m;i++)55 {56 scanf("%s", &s); 57 if (flag) continue;58 int x = s[0] - ‘A‘;59 int y = s[2] - ‘A‘;60 g[x][y] = 1;61 indegree[y]++; //y的入度+162 int p = tuopu();63 if (p == 0)64 {65 printf("Inconsistency found after %d relations.\n", i);66 flag = 1;67 }68 if (p == 1)69 {70 printf("Sorted sequence determined after %d relations: ", i);71 for (int j = 0; j < n; j++)72 printf("%c", ans[j] + ‘A‘);73 printf(".\n");74 flag = 1;75 }76 }77 if (!flag)78 printf("Sorted sequence cannot be determined.\n");79 }80 return 0;81 }
POJ 1094 Sorting It All Out
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。