#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int n,m;
int link[26][26];
int in[26];
struct node
{
    int num,p;
}a[26];
bool cmp(node a,node b)
{
    return a.num>b.num;
}
void init()
{
    memset(link,0,sizeof(link));
    memset(in,0,sizeof(in));
    int ii,way=0;
    char st[10];
    for(ii=1;ii<=m;ii++)
    {
        scanf("%s",st);
        int s=st[0]-'A',t=st[2]-'A';
        if(link[s][t]||s==t)
        {
            way=2;
            break;
        }
        if(link[t][s])continue;
        link[t][s]=1;
        in[s]++;
        for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        if(link[i][k]&&link[k][j]&&link[i][j]==0)
        {
            link[i][j]=1;
            in[j]++;
            if(link[j][i])
            {
                way=2;
                goto XXX;
            }
        }
        int num=0;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        if(link[i][j]) num++;
        if(num==n*(n-1)/2)
        {
            way=1;
            for(int k=0;k<n;k++)
            {
                a[k].p=k;
                a[k].num=in[k];
            }
            sort(a,a+n,cmp);
            break;
        }

    }
    XXX:
    if(way==2) printf("Inconsistency found after %d relations.\n",ii);
    if(way==1)
    {
        printf("Sorted sequence determined after %d relations: ",ii);
        for(int i=0;i<n;i++)printf("%c",'A'+a[i].p);
        puts(".");
    }
    for(ii++;ii<=m;ii++)scanf("%s",st);
    if(way==0) printf("Sorted sequence cannot be determined.\n");

}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m),n+m)init();
     
    return 0;
}

• Re:【无需拓扑排序，floyd即可】贴代码 (1862) xsc351072127 2013-03-17 00:57:26