首页 > 代码库 > POJ1094-Sorting It All Out-拓扑排序
POJ1094-Sorting It All Out-拓扑排序
【题目大意】：
给出 A“<”B 的关系图
①在第i个关系之chu后，得出XXXX
②在第i个关系之后 出现错误（环）
③全部关系之后仍然无法排序
【解题思路】：1.读一个数判断是否是②情况。
2.利用Floyd更新 任意两元素之间关系，当更新数达到（n*n-n）/2 之后，得到①情况。
3.数据全部读入之后，仍没有答案，得到③情况。
1 #include "cstdio" 2 #include "iostream" 3 #include "cstring" 4 using namespace std; 5 int E[30][30]; 6 int sum[30]; 7 void putout(int n) 8 { 9 int s;10 for (int i = 1; i <= n; i++)11 {12 s = 1;13 for (int j = 1; j <= n; j++)14 if (E[i][j] && i != j) s++;15 sum[s] = i;16 }17 for (int i = n; i >= 1 ; i--)18 {19 printf("%c", sum[i] + ‘A‘ - 1);20 }21 22 }23 int main()24 {25 int n , m;26 bool wait;27 int ans = 0;28 while (cin >> n >> m && (n + m))29 {30 memset(E, 0, sizeof(E));31 char a, b;32 wait = true;33 ans = (n * n - n) / 2;34 for (int i = 1; i <= m ; i++)35 {36 scanf(" %c"<"%c", &a, &b);37 38 if (wait)39 {40 if (E[b - ‘A‘ + 1][a - ‘A‘ + 1] == 1 || (a - ‘A‘ + 1) == (b - ‘A‘ + 1))41 {42 wait = false;43 printf("Inconsistency found after %d relations.\n", i);44 continue;45 }46 if (E[a - ‘A‘ + 1][b - ‘A‘ + 1] == 0)47 {48 E[a - ‘A‘ + 1][b - ‘A‘ + 1] = 1;49 ans--;50 }51 for (int k = 1 ; k <= n ; k++)52 for (int j = 1; j <= n; j++)53 for (int z = 1; z <= n; z++)54 if (E[j][z] == 0 && E[j][k] == 1 && E[k][z] == 1 && (j != z))55 {56 ans--;57 E[j][z] = 1;58 }59 if (!ans)60 {61 wait = false;62 printf("Sorted sequence determined after %d relations: ", i);63 putout(n);64 printf(".\n");65 continue;66 }67 }68 }69 if (wait) printf("Sorted sequence cannot be determined.\n");70 }71 }
POJ1094-Sorting It All Out-拓扑排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。