#include<iostream>
#include<cstdio>
using namespace std;

int v,e,seqi,ei;
bool end;
int from[2000000],to[2000000];
int map[30][30],seq[30],mark[30];

bool init()
{
    char t,q;
    ei=0;
    end=false;
    memset(map,0,sizeof(map));
    for(int i=0;i<e;i++)
    {
        cin>>t>>q>>q;
        from[ei]=t-'A';
        to[ei]=q-'A';
        ei++;
    }
    return true;
}
bool dfs(int pos)
{
    if(mark[pos]==1)
    {
        end=true;
        return end;
    }
    else if(mark[pos]==0)
    {
        mark[pos]=1;
        for(int i=0;i<v;i++)
            if(map[pos][i] && mark[i]!=-1)
                if(dfs(i))
                    break;
    }
    mark[pos]=-1;
    seqi--;
    seq[seqi]=pos;
    return end;
}
void test_seq(int t)
{
    int i;
    for(i=0;i<v-1;i++)
        if(!map[i][i+1])
            break;
    if(i==v-1)
    {
        end=true;
        printf("Sorted sequence determined after ");
        printf("%d relations: ",t+1);
        for(int j=0;j<v;j++)
            printf("%c",(char)(seq[j]+'A'));
        printf(".\n");
    }
}
void toposort(int t)
{
    int i;
    seqi=v;
    memset(mark,0,sizeof(mark));
    for(i=0;i<v;i++)
        if(mark[i]==0)
            if(dfs(i))
                break;
    if(i<v)
    {
        printf("Inconsistency found after %d relations.\n",t+1);
        return ;
    }
    test_seq(t);
}
void solve()
{
    int i;
    for(i=0;i<ei && !end;i++)
    {
        map[from[i]][to[i]]=1;
        toposort(i);
    }
    if(!end)
        printf("Sorted sequence cannot be determined.\n");
}
int main()
{
    while(scanf("%d%d",&v,&e),v)
    {
        init();
        solve();
    }
    system("pause");
    return 0;
}

• 啊啊啊，原来是这个。。。太惨了，这题居然因为这个原因，让我郁闷了一个月，悲剧。 (1977) lizeliang 2009-09-19 21:11:56