POJ1094(拓扑排序)

题目：POJ1094

大致题意就是多组输入，输入n，m（可以视为n个点，有m个关系）m个关系在字母A-Z范围内，给你一些关系比如A<B，就认为A到B之间有条有向路，可以分三种情况：

1.当出现了一组关系使图出现了环，则输出“Inconsistency found after K1 relations” 其中的K1就是在第几个关系出现了环，后面的关系就可以忽略不处理了

2.当还未输入完给的关系就确定了，n个点的关系，则后面的关系就不用处理了，直接输出“Sorted sequence determined after K2 relations: （点关系的顺序）.” K2是此时确定关系的点的个数；

3.当输入完给的关系，还未确定n个点的关系，则输出“Sorted sequence cannot be determined.”

代码如下：

#include<stdio.h>
#include<string.h>
char a[5];
int pre[300][300];//存放村庄之间的关系 1即相通（单向）0即无路
int vis[1000],b[1000],c[1000];//vis记录通向该点的关系数（即入度）c[]存放确定关系的点
int n,m;
int tuopu()
{
	int rem,FLAG=1;
	for(int i=0;i<n;i++)
		b[i]=vis[i];
	int g=0;
	for(int i=0;i<n;i++)
	{
	
		int res=0;	
		for(int j=0;j<n;j++)
		{
			if(b[j]==0){
				res++;
				rem=j;
			}
		}
		if(res>1) //说明多个入度为零的点 即n个点的顺序不确定
		{
			FLAG=-1;
		}
		if(res==0) return -2;//无入度为零的点 即出现环
		b[rem]=-1;//把找到的入度为零的点 标记为-1 表示访问过了
		c[g++]=rem;
		for(int k=0;k<n;k++)
			if(pre[rem][k])	b[k]--;	//把入度为零的点 它的出边去掉
	}
	return FLAG;
}
int main()
{
	
	while(~scanf("%d%d",&n,&m)&&(n+m))
	{
		memset(vis,0,sizeof(vis));
		memset(pre,0,sizeof(pre));
		int ans=0;
		for(int i=0;i<m;i++) 
		{
			scanf("%s",a);
			if(ans) continue;//ans 如果是1 则说明已经出结果了，下面的关系就不用处理了。直接跳过即可
			if(pre[a[0]-'A'][a[2]-'A']==0)//防止重边
			{
				pre[a[0]-'A'][a[2]-'A']=1;
				vis[a[2]-'A']++;//记录 a[2]点的入度个数
			}
			int s=tuopu();
			if(s==-2)//即出现环了
			{
				
				printf("Inconsistency found after %d relations.\n",i+1);//即输出第几个关系出现了环
				ans=1;
			 }
			if(s==1)
			{
				printf("Sorted sequence determined after %d relations: ",i+1);
				for(int i=0;i<n;i++)	
					printf("%c",c[i]+'A');
				puts(".");
				ans=1;
			}
		}
		if(!ans)
			printf("Sorted sequence cannot be determined.\n");	
	}
	return 0;
}