拓扑排序。
每次输入一个关系就进行一次拓扑排序，若得出结果则以后不再进行。 若找不到入度为零的点且存在未删除的点，则一定有环。 若入度为零的点超过一个，则无序，但还需继续判断是否矛盾。
注意： 矛盾的优先级大于无序。 degree 在topsort需要用临时数组。
#include <iostream> #include <cstdlib> #include <cstdio> #include <vector> #include <cstring> using namespace std; const int MAX = 26; int n, m; int indeg[MAX+1]; bool joint[MAX+1][MAX+1]; vector<int> road[MAX+1]; vector<int> zero_indeg; vector<int> sequence; int readchar() { int t; while (t = getchar()) { if (isalpha(t)) break; } return t; } void _delete(int x, int *temp_indeg) { for (int i = 0; i < road[x].size(); i++) temp_indeg[road[x][i]]--; temp_indeg[x] = -1; } int top_sort() { sequence.clear(); int temp_indeg[MAX+1]; for (int i = 1; i <= MAX; i++) temp_indeg[i] = indeg[i]; int flag = 1; while (sequence.size() < n) { zero_indeg.clear(); for (int i = 1; i <= n; i++) { if (!temp_indeg[i]) zero_indeg.push_back(i); } int sz = zero_indeg.size(); if (!sz) return -1; // circle else { if (sz > 1) flag = 0; for (int i = 0; i < sz; i++) { sequence.push_back(zero_indeg[i]); _delete(zero_indeg[i], temp_indeg); } } } return flag; } int main() { int sign; int cnt; while (scanf("%d%d", &n, &m) && (n || m)) { char a; char b; sign = 0; cnt = 0; memset(indeg, 0, sizeof(indeg)); memset(joint, 0, sizeof(joint)); for (int i = 1; i <= MAX; i++) road[i].clear(); for (int i = 1; i <= m; i++) { a = readchar() - 'A' + 1; getchar(); b = getchar() - 'A' + 1; if (!joint[a][b]) { joint[a][b] = true; road[a].push_back(b); indeg[b]++; if(!sign) { sign = top_sort(); cnt++; } } } if (sign == 1) { printf("Sorted sequence determined after %d relations: ", cnt); for (int i = 0; i < n; i++) printf("%c", sequence[i] - 1 +'A'); printf(".\n"); } else if (sign == -1) { printf("Inconsistency found after %d relations.\n", cnt); } else if (!sign) { printf("Sorted sequence cannot be determined.\n"); } } return 0; }