大意:给你一些关系,输出拓扑序列,如果有环,讨论一下;如果有多种情况,讨论一下;如果那两种都不是,输出拓扑序列。
思路:没什么好说的,就是一个求拓扑序列。
1 #include <map> 2 #include <stack> 3 #include <queue> 4 #include <math.h> 5 #include <stdio.h> 6 #include <string.h> 7 #include <iostream> 8 #include <limits.h> 9 #include <algorithm> 10 #define LL long long 11 #define min(a,b) (a>b?b:a) 12 #define max(a,b) (a>b?a:b) 13 #define eps 1e-9 14 #define INF 0x3f3f3f3f 15 using namespace std; 16 17 int n, m; 18 int Map[30][30], dis[30], Ans[30], tem[30]; 19 20 int Topo() 21 { 22 stack<int>s; 23 memcpy(tem, dis, sizeof(dis)); 24 for(int i = 0; i < n; i++) 25 { 26 if(!tem[i]) 27 { 28 s.push(i); 29 } 30 } 31 int cnt = 0; 32 bool flag0 = false; 33 while(!s.empty()) 34 { 35 if(s.size() > 1) 36 { 37 flag0 = true; 38 } 39 int temp = s.top(); 40 Ans[cnt++] = temp; 41 s.pop(); 42 for(int i = 0; i < n; i++) 43 { 44 if(Map[temp][i] && --tem[i] == 0) 45 { 46 s.push(i); 47 } 48 } 49 } 50 if(cnt != n) 51 { 52 return 1; 53 } 54 else if(flag0) 55 { 56 return 2; 57 } 58 return 0; 59 } 60 61 void Solve() 62 { 63 while(~scanf("%d%d", &n, &m) && (n ||m)) 64 { 65 bool flag1 = false, flag2 = false; 66 memset(Map, 0, sizeof(Map)); 67 memset(dis, 0, sizeof(dis)); 68 for(int i = 1; i <= m; i++) 69 { 70 char str[3]; 71 scanf("%s", str); 72 if(!flag1 &&!flag2) 73 { 74 if(Map[str[2]-‘A‘][str[0]-‘A‘] == 1) 75 { 76 flag2 = true; 77 printf("Inconsistency found after %d relations.\n", i); 78 continue; 79 } 80 if(!Map[str[0]-‘A‘][str[2]-‘A‘]) 81 { 82 Map[str[0]-‘A‘][str[2]-‘A‘] = 1; 83 dis[str[2]-‘A‘]++; 84 } 85 int flag = Topo(); 86 if(!flag) 87 { 88 printf("Sorted sequence determined after %d relations: ", i); 89 for(int j = 0; j < n; j++) 90 { 91 printf("%c", Ans[j]+‘A‘); 92 } 93 printf(".\n"); 94 flag1 = true; 95 } 96 else if(flag == 1) 97 { 98 printf("Inconsistency found after %d relations.\n", i); 99 flag2= true; 100 } 101 } 102 } 103 if(!flag1 &&!flag2) 104 { 105 printf("Sorted sequence cannot be determined.\n"); 106 } 107 } 108 } 109 110 int main(void) 111 { 112 Solve(); 113 114 return 0; 115 }