#include<iostream.h>
#include<string.h>

char letter[26];
int n,m,p,q,indeg[26],relation[26][26],tmpindeg[26],flag,out[26];

int search(char *let,char letter)//判断结点在数组中的序号
{
	int h=0;
	while(h<n&&let[h]!=letter)
		h++;
	return h;
}

/*--------拓扑排序--------*/
void topusort(int *indeg,int *t)
{
	memset(out,-1,sizeof(out));
	int total,tmpadd,totaln=0;
	for(p=0;p<n;p++)
	{
		if(indeg[p]<0) continue;
		total=0;
		for(q=0;q<n;q++)
			if(indeg[q]==0)
			{
				total++;
				tmpadd=q;
			}//入度为0的结点的个数
		if(total==0)//如果在某一次输入后入度为0的结点的个数为0，即图中存在环，本次排序肯定失败
		{
			flag=*t;
			break;
		}
		else if(total>1)//如果在某一次输入后入度为0的结点的个数大于1，则无法判断，继续本次排序
		{
			flag=0;
			break;
		}
		else if(total==1)//入度为0的结点的个数为1，则将该结点的序号传给 out数组
		{
			out[totaln]=tmpadd;//保存输出序列
			totaln+=1;
			if(totaln==n)
				flag=*t;
			else flag=0;
			indeg[tmpadd]=-1;//标志该结点已经处理
			for(q=0;q<n;q++)
				if(relation[q][tmpadd]==1)
					indeg[q]--;
		}
	}
}
void main()
{
	char instr[4];
	int add1,add2,totaln,i;
	cin>>n>>m;
	while(n!=0||m!=0)
	{ 
		memset(relation,0,sizeof(relation));
		memset(letter,0,sizeof(letter));
		memset(indeg,-1,sizeof(indeg));
		totaln=0;//已经出现的结点个数
		flag=0;
		for(i=1;i<=m;i++)
		{
			cin>>instr;
			if(flag==0)
			{
				add1=search(letter,instr[0]);
				add2=search(letter,instr[2]);		
				if(add1==n)
				{
					add1=totaln;
					totaln++;
					indeg[add1]=0;
				}
				if(add2==n)
				{
					add2=totaln;
					totaln++;
					indeg[add2]=0;
				}//如果该结点是第一次出现

				letter[add1]=instr[0];
				letter[add2]=instr[2];//保存结点信息

				relation[add2][add1]=1;
				indeg[add2]+=1;
				for(p=0;p<26;p++)
					tmpindeg[p]=indeg[p];//复制一个入度数组传给排序函数		
				topusort(tmpindeg,&i);
			}
			else continue;
		}
		if(flag==0&&i==m+1)
			cout<<"Sorted sequence cannot be determined."<<endl;
		else if(p!=n&&i==m+1)
			cout<<"Inconsistency found after "<<flag<<" relations."<<endl;
		else if(p==n&&i==m+1)
		{
			cout<<"Sorted sequence determined after "<<flag<<" relations: ";
			for(i=0;i<n;i++)
				cout<<letter[out[i]];
			cout<<"."<<endl;
		}
		cin>>n>>m;
	}
}

• 自己顶啦!郁闷几天了 (2370) acmcc 2004-05-28 17:12:01