POJ 1094 Sorting It All Out（经典拓扑+邻接矩阵）

(￣▽￣)"

//判环：当入度为0的顶点==0时，则有环（inconsistency）
//判序：当入度为0的顶点仅为1时，则能得到有序的拓扑排序，否则无序
//边输入边判断，用continue来做到：得出结果后，对后续的输入不作处理
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

const int MAXN=30;
int g[MAXN][MAXN];
int degree[MAXN],L[MAXN],n,m;
char ch[5];

int toposort()
{
    int tot=0,point,in,flag=1;//flag==1:有序，flag==-1:无序（即不确定）
    int t[MAXN]; //由于是边输入边判断，所以用t数列来保存当前（0到i）的顶点入度情况，以此避免修改degree数组
    for(int i=1;i<=n;i++)
        t[i]=degree[i];
    for(int i=1;i<=n;i++)
    {
        in=0;
        for(int j=1;j<=n;j++)
            if(!t[j])
            {
                in++;
                point=j;
            }
        if(in==0) return 0;
        if(in>1) flag=-1;
        L[tot++]=point; //入度为0的点入队
        t[point]=-1; //删点
        for(int j=1;j<=n;j++)
            if(g[point][j]==1)
                t[j]--;  //删边
    }
    return flag;
}

void init_input_judge_output()
{
    int sign=0;
    memset(degree,0,sizeof(degree));
    memset(L,0,sizeof(L));
    memset(g,0,sizeof(g));
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ch);
        if(sign) continue;
        int a=ch[0]-'A'+1;
        int b=ch[2]-'A'+1;
        g[a][b]=1;
        degree[b]++;
        int judge=toposort();
        if(judge==0)
        {
            printf("Inconsistency found after %d relations.
",i);
            sign=1;
        }
        if(judge==1)
        {
            printf("Sorted sequence determined after %d relations: ",i);
            for(int j=0;j<n;j++)
                printf("%c",L[j]+'A'-1);
            printf(".
");
            sign=1;
        }
    }
    if(!sign)
        printf("Sorted sequence cannot be determined.
");
}

int main()
{
    while(scanf("%d%d",&n,&m)&&n+m)
    {
        init_input_judge_output();
    }
    return 0;
}