学步园

拓扑排序：若G包含有向边(U,V)，则在序列中U出现在V之前，即该序列使得图中所有有向边均从左指向右。如果图是有回路的，就不存在这样的序列。

　　首先选择一个无前驱的顶点(即入度为0的顶点，图中至少应该有一个这样的顶点，否则肯定存在回路)，然后从图中移去该顶点以及由其发出的所有有向边，如果图中还存在无前驱的顶点，则重复上述操作，直到操作无法进行。如果图不为空，说明图中存在回路，无法进行拓扑排序；否则移出的顶点的顺序就是对该图的一个拓扑排序。

具体思路：

　　每输入一组偏序关系进行一次拓扑排序。

　　如果存在回路，输出矛盾。

　　在不存在回路的基础上，判断每次入度为0的点是否唯一，只有保证每次只有一个点入度为0，才能保证最终的序列唯一。

注意：如果对于某一次输入已经能确定序列矛盾或者序列完全有序，则可以忽略后面的输入。

Description

Input

Output

Sample Input

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<stdlib.h>
using namespace std;
#define maxv 27
#define maxe 101
int n,m,size,head[maxv],indegree[maxv],ans,indegree1[maxv];
vector<int>vv;
struct edge
{
    int v,next;
}edges[maxe];
void init()
{
    size=0;
    memset(head,-1,sizeof(head));
	memset(indegree,0,sizeof(indegree));
}
void insert(int u,int v)
{
    edges[size].v=v;
    edges[size].next=head[u];
    head[u]=size++;
    indegree[v]++;
}
int tsort()
{
    int i,flag=0;
    queue<int>q;
    vv.clear();
    memcpy(indegree1,indegree,n*sizeof(int));
//注意这里是对indegree1操作，不影响indegree，也就是用indegree1代替indegree操作，因为indegree要减1，会影响下一步
    for(i=0;i<n;i++)
        if(indegree1[i]==0)
            q.push(i);
    while(!q.empty())
    {
        if(q.size()>1) flag=1;
        int w=q.front();
        q.pop();
        vv.push_back(w);
        
        for(int i=head[w];i!=-1;i=edges[i].next)
        {
            indegree1[edges[i].v]--;
            if(indegree1[edges[i].v]==0)
                q.push(edges[i].v);
        }
    }
    if(vv.size()!=n) return 1;
    if(flag) return 0;
    return 2;
}
int main()
{
    int i,j;
    char s[4];
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
       init();
       ans=0;
       for(i=0;i<m&&!ans;i++)
       {
           scanf("%s",s);
           int a=s[0]-'A',b=s[2]-'A';
           insert(a,b);
           ans=tsort();
       }
       for(j=i;j<m;j++) scanf("%s",s);
       switch(ans)
       {
           case 0:printf("Sorted sequence cannot be determined.\n");break;
           case 1:printf("Inconsistency found after %d relations.\n",i);break;
           case 2:printf("Sorted sequence determined after %d relations: ",i);
           for(i=0;i<n;i++)
           {
               printf("%c",vv[i]+'A');
           }
           printf(".\n");
           break;
       }
    }
    return 0;
}