poj1094——Sorting It All Out

拓扑排序！具体方法见：http://www.cnblogs.com/xiaosuo/archive/2010/03/26/1690302.html

#include<stdio.h>
#include<string.h>
struct node
{
   int u,v;
}tt[1000];
int n,m,k,dgree[27],queue[1000],rear,front;
bool flag,flag1,edge[27][27],vis[27];
void NPFTP()
{
	int i;
	bool equal=true;
	rear=0;front=0;
	memset(edge,true,sizeof(edge));
	memset(dgree,0,sizeof(dgree));
	memset(vis,true,sizeof(vis));
	for(i=1;i<=k;i++){
		if(edge[tt[i].u][tt[i].v]){
			edge[tt[i].u][tt[i].v]=false;
			dgree[tt[i].v]+=1;
		}
	}
	for(i=1;i<=n;i++)
		if(dgree[i]==0){
			queue[++rear]=i;
			vis[i]=false;
		}
		if(rear>1)
			equal=false;
	memset(edge,true,sizeof(edge));
	while(rear!=front)
	{
		front++;;
		for(i=1;i<=k;i++){
			if(tt[i].u==queue[front]&&edge[tt[i].u][tt[i].v]){
				edge[tt[i].u][tt[i].v]=false;
				dgree[tt[i].v]--;
			}
		}
		for(i=1;i<=n;i++)
			if(dgree[i]==0&&vis[i]){
				vis[i]=false;
				queue[++rear]=i;
			}
			if(rear-front>1)
				equal=false;
	}
	if(rear==n&&equal){
		flag1=false;flag=false;
		printf("Sorted sequence determined after %d relations: ",k);
	    for(i=1;i<=rear;i++)
					printf("%c",queue[i]-1+'A');
				printf(".\n");
			}
	else if(rear<n){
		flag1=false;flag=false;
		printf("Inconsistency found after %d relations.\n",k);
			}	
}
int main()
{
	int i,j;
	char p[5];
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		flag=true;flag1=true;
		if(n==0&&m==0)
			break;
		for(k=1;k<=m;k++)
		{
			scanf("%s",&p);
			tt[k].u=p[0]-'A'+1;tt[k].v=p[2]-'A'+1;
		}
		for(k=1;k<=m;k++)
		{
			if(flag1)
				NPFTP();
		}
		if(flag)
			printf("Sorted sequence cannot be determined.\n");
	}
	return 0;
}