//拓扑排序,邻接阵形式,复杂度O(n^2)
//如果无法完成排序,返回0,否则返回1,ret返回有序点列
//传入图的大小n和邻接阵mat,不相邻点边权0
#include<iostream>
using namespace std;
#define maxn 30
int mat[maxn][maxn],ret[maxn],d[maxn],n,num;
int stack[maxn*10];
bool stat[maxn];

bool toposort( )
{
	int i,j,pos,top=0,t=0;
	for(i=0;i<n;i++)
		for(d[i]=j=0;j<n;j++)
			if(mat[j][i]==1)d[i]++;
	//memset(stack,-1,sizeof(stack));

	for(top=i=0;i<n;i++)
		if(!d[i]&&stat[i])
		{
			pos=i;t++;
		}
	if(t==1)stack[top++]=pos;
	else if(t>1)return false;
	while(top>0)
	{
		pos=stack[--top];
		ret[num++]=pos;d[pos]=-1;
		for(i=0;i<n;i++)
			if(mat[pos][i]==1)d[i]--;

		for(t=i=0;i<n;i++)
			if(!d[i]&&stat[i])
			{
				pos=i;t++;
			}
		if(t==1)stack[top++]=pos;
		else if(t>1) return false;
	}
	if(num==n)return true;

	return false;
}
	                                              

int main( )
{
	int i,j,m,a,b;
	char s[5],c; bool flag;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(!m&&!n)break;
		flag=true;num=0;
		memset(ret,0,sizeof(ret));
		memset(mat,0,sizeof(mat));
		memset(stat,0,sizeof(stat));

		for(i=1;i<=m;i++)
		{
			scanf("%s",s);
			a=s[0]-'A';b=s[2]-'A';
			stat[a]=true;stat[b]=true;
			mat[a][b]=1;
			if(toposort( )&&flag)
			{
				flag=false;
				printf("Sorted sequence determined after %d relations: \n",i);
				for(j=0;j<n;j++)
				{
					c=ret[j]+'A';
					printf("%c",c);
				}
				printf("\n");
			}
			else
			{
				memset(ret,0,sizeof(ret));
				num=0;
			}
		}
		num=0;memset(ret,0,sizeof(ret));
		toposort( );
		if(!num&&flag)printf("Inconsistency found after %d relations.\n",m);
		else if(num&&num<n&&flag)
				printf("Sorted sequence cannot be determined.\n");
	}

	return 0;
}

• Re:崩溃了...........disguss里提到的数据都过了丫,怎么还是WA啊 (8) ghk 2008-10-11 13:49:48