This post is written in Chinese. Please consider using Google Translate

基本方法是拓扑排序，非常容易错。首先逐条读入关系，每读入一个关系，进行一次拓扑排序。拓扑排序可能返回三种结果，有确定唯一的顺序，无法确定唯一的顺序，有矛盾（存在环）。注意只要一但确定了唯一的顺序，立刻判定输出，即使后面的条件有矛盾也要忽略了。 例如下面数据 2 2 A<B B<A

答案是Sorted sequence determined after 1 relations: AB.

有一些需要注意的细节，在拓扑排序中，判断存在环的优先级要高于无法确定唯一的顺序的优先级。例如下面数据 4 4 A<B C<B D<B B<A 0 0

答案是Inconsistency found after 1 relations.

还有就是多组测试数据变量一定要清零，我就是因为没有清零错误了好几次。

/* 
 * Problem: pku1094 Sorting It All Out
 * Author: Guo Jiabao
 * Time: 2009.4.7 10:41
 * State: Solved
 * Memo: 拓扑排序
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=27;
using namespace std;
int N,M;
bool adjm[MAXN][MAXN];
int ind[MAXN];
char order[MAXN];
int topsort()
{
    int k,i,j;
    bool det=true;
    memset(ind,0,sizeof(ind));
    memset(order,0,sizeof(order));
    for (i=1;i<=N;i++)
        for (j=1;j<=N;j++)
            if (adjm[i][j])
                ind[j]++;
    for (k=1;k<=N;k++)
    {
        i=0;
        for (j=1;j<=N;j++)
            if (ind[j]==0)
            {
                if (i==0)
                    i=j;
                else
                    det=false;
            }
        if (i==0)
            return 1;
        ind[i]=-1;
        order[k-1]=i+'A'-1;
        for (j=1;j<=N;j++)
            if (adjm[i][j])
                ind[j]--;
    }
    if (det)
        return 0;
    else
        return 2;
}
void solve()
{
    int i,a,b,rs,sure=false;;
    char C[4];
    memset(adjm,0,sizeof(adjm));
    for (i=1;i<=M;i++)
    {
        scanf("%s",&C);
        a=C[0]-'A'+1;b=C[2]-'A'+1;
        if (sure) continue;
        adjm[a][b]=true;
        rs=topsort();//0确定唯一 1矛盾 2不唯一/不完全
        if (rs==0)
        {
            printf("Sorted sequence determined after %d relations: %s.n",i,order);
            sure=true;
        }
        else if (rs==1)
        {
            printf("Inconsistency found after %d relations.n",i);
            sure=true;
        }
    }
    if (!sure)
        printf("Sorted sequence cannot be determined.n");
}
int main()
{
    freopen("siao.in","r",stdin);
    freopen("siao.out","w",stdout);
    while (scanf("%d%d",&N,&M),!(N==0 && M==0))
        solve();
    return 0;
}