题目链接。
题目大意:
给定一定的数量的小于关系：
1.如果发现环，输出从前几次就可以确定出现环
2.如果能够确定唯一序列，输出。
3.如果通过全部关系，还不能确定序列，则输出不能确定.
分析:
个人感觉难点在于判环上。
1.如果每次都只能找到1个入度为0的点，并能确定序列，则该序列即为答案。
2.如果每次查找时，发现两个及其以上的入度为0的点，则表明一定不能确定唯一序列（即存在环或者是不能确定）。如果可以确定一个任意序列，即表明还需要更多关系。如果继续查找下去，找不到入度为0的点，则存在环。
AC代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue> using namespace std; const int maxn = ;
const int INF = (<<); int n, m, indeg[maxn], S[maxn], top, mark;
bool G[maxn][maxn], v[maxn]; int toposort()
{
int deg[maxn], cn;
bool vis[maxn], flag = true; top = ;
memcpy(deg, indeg, sizeof(deg));
memset(vis, , sizeof(vis)); for(int i=; i<n; i++)
{
cn = ; for(int k=; k<n; k++) if(deg[k] == ) cn++; //计算入度为0的点的个数 if(cn > ) flag = false; //出现环或者不能确定唯一序列
else if(cn == ) break; //出现环 int k;
for(k=; k<n; k++) if(deg[k] == ) break;
S[top++] = k;
deg[k]--;
for(int j=; j<n; j++) if(G[k][j]) deg[j]--;
} if(cn == ) return -; //环
if(mark < n || !flag) return ; //不能判断
else return ; //拓扑成功
} int main()
{
char c1, c2;
int flag, num;
// freopen("my.txt", "r", stdin);
while(scanf("%d %d", &n, &m) == )
{
if(n == && m == ) break; memset(indeg, , sizeof(indeg));
memset(G, false, sizeof(G));
memset(v, false, sizeof(v)); flag = ;
mark = ; for(int i=; i<m; i++)
{
getchar();
scanf("%c<%c", &c1, &c2); if(!G[c1-'A'][c2-'A']) {
G[c1-'A'][c2-'A'] = true;
indeg[c2-'A']++;
} //mark用来标记当前已经出现的字母的个数
if(!v[c1-'A']) { v[c1-'A'] = true; mark++; }
if(!v[c2-'A']) { v[c2-'A'] = true; mark++; } int res;
if(flag == ) {
res = toposort(); if(res == -) {
flag = -;
num = i;
} else if(res == ) {
num = i;
flag = ;
}
}
} if(flag == ) {
printf("Sorted sequence determined after %d relations: ", num+);
for(int i=; i<top; i++)
{
putchar(S[i]+'A');
}
printf(".\n");
}
else if(flag == ) printf("Sorted sequence cannot be determined.\n");
else printf("Inconsistency found after %d relations.\n", num+);
} return ;
}