Sorting It All Out
题目链接：http://poj.org/problem?id=1094
题目大意：
输入N，M。N代表有几个字母（从A开始为第一个），M代表有几个关系。关系形如：A<B。
现在问你能否进行拓扑排序，如果可以，拓扑排序是否唯一。
样例：
输入：
4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0
输出：
Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.
解题思路：
这道题目略坑啊。题目的意思是输入一个关系要进行一次判断，如果可以拓扑排序，且答案唯一，就判为可以排序。如果无法排序，就判为矛盾。且不再处理之后的输入。
至于判断拓扑排序是否唯一，只需看相邻的两个字母是否有前后关系即可。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = 30;
int n, m, g[maxn][maxn], du[maxn];
char L[maxn];
vector<int> v[maxn];
bool toposort() {
int tot = 0;
queue<int> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < v[i].size(); j++) du[v[i][j]]++;
for (int i = 0; i < n; i++) if (!du[i]) q.push(i);
while(!q.empty()) {
int x = q.front(); q.pop();
L[tot++] = x + 'A';
for (int i = 0; i < v[x].size(); i++) {
int u = v[x][i];
du[u]--;
if (!du[u]) q.push(u);
}
}
if (tot == n) return 1;
return 0;
}
int main () {
char A, O, B;
while(scanf("%d%d", &n, &m)) {
if (!n && !m) break;
mem(g, 0);
mem(L, 0);
int incon = 0, ok = 0;
for (int i = 0; i < n; i++) {
v[i].clear();
du[i] = 0;
}
for (int i = 1; i <= m; i++) {
getchar();
scanf("%c<%c", &A, &B);
if (ok || incon) continue;
int x = A - 'A', y = B - 'A';
if (g[y][x]) incon = i;
else {
g[x][y] = 1;
v[x].push_back(y);
if (toposort()) {
int j;
for (j = 0; j < n - 1; j++) if (g[L[j] - 'A'][L[j + 1] - 'A'] == 0) break;
if (j == n - 1) ok = i;
}
else incon = i;
}
}
if (ok) printf("Sorted sequence determined after %d relations: %s.\n", ok, L);
else if (incon) printf("Inconsistency found after %d relations.\n", incon);
else printf("Sorted sequence cannot be determined.\n");
}
return 0;
}