pku 1094 Sorting It All Out 拓扑排序

左手的ㄟ右手 2022-08-09 13:52 163阅读 0赞

\#include <iostream> \#include <stack> using namespace std; int edge\[27\]\[27\]; //图的邻接矩阵 int in\_degree\[27\]; //顶点的入度 bool flagDegree\[27\]; char strRet\[27\]; int n, m; //拓扑排序 //-1: 继续 //0: 完成排序 //1: 有回路 int TopoOrder() \{ stack<int> s; memset(in\_degree, 0, sizeof(in\_degree)); memset(strRet, 0, sizeof(strRet)); memset(flagDegree, 0, sizeof(flagDegree)); for (int i = 1; i <= 26; ++i) for (int j = 1; j <= 26; ++j) \{ if(edge\[i\]\[j\]) \{ flagDegree\[i\] = flagDegree\[j\] = 1; in\_degree\[j\]++; \} \} for (int i = 1; i <= 26; ++i) if(flagDegree\[i\] && !in\_degree\[i\]) s.push(i); int cnt = 0; bool flagCannotDetermined = 0; while(!s.empty()) \{ if(s.size() > 1) flagCannotDetermined = 1; int temp = s.top(); strRet\[cnt++\] = 'A'+temp-1; s.pop(); for(int i = 1; i <= 26; ++i) if(edge\[temp\]\[i\] && (--in\_degree\[i\]) == 0) s.push(i); \} strRet\[cnt\] = '/0'; for(int i = 1; i <= 26; ++i) if(flagDegree\[i\] && in\_degree\[i\]) return 1; if(flagCannotDetermined) return -1; if(cnt == n) return 0; return -1; \} int main() \{ char str\[4\]; int i; while (scanf("%d%d", &n, &m) && !(n==0&&m==0)) \{ memset(edge, 0, sizeof(edge)); bool flagOver = 0, flagCircle = 0, flagNotDetermined = 0; int index; for (i = 1; i <= m; ++i) \{ cin >> str; edge\[str\[0\]-'A'+1\]\[str\[2\]-'A'+1\] = 1; if(flagCircle || flagNotDetermined || flagOver) continue; int ret = TopoOrder(); if(ret == 0) \{ flagOver = 1; index = i; \} else if(ret == 1) \{ flagCircle = 1; index = i; \} if(i == m && ret == -1) flagNotDetermined = 1; \} if(flagCircle) printf("Inconsistency found after %d relations./n", index); else if(flagNotDetermined) printf("Sorted sequence cannot be determined./n"); else printf("Sorted sequence determined after %d relations: %s./n", index, strRet); \} return 0; \} //这组数据拯救了我,贡献出来 /\* 6 8 A<B A<C B<D C<E D<E E<D D<F E<F Right Answer: Inconsistency found after 6 relations. Wrong Answer: Sorted sequence cannot be determined. 原因是: 判断有回路的优先级比判断不可排序的优先级高. 判断不可排序就会返回去录入新的一组值. 我是这样才行的. if(s.size() > 1) flagCannotDetermined = 1; 而不可以直接return -1;//-1代表继续. \*/