4676324_ac_16ms_292k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 92 行

#include<iostream>
using namespace std;
int n,m;
int map[28][28];
int du[28],dus[28];
int q[28],ql;
bool used[28];
char input[10];
int result;
bool weiyi;
int outline[28];
bool done;
void testout()
{
	for(int count=1;count<=n;count++) cout<<dus[count]<<" ";
		cout<<endl;
}
int pick()
{
	int sum=0,re=0;
	for(int count=1;count<=n;count++) 
		if(dus[count]==0&&used[count]==false) 
		{
			sum++;
			re=count;
		}
	if(sum>1) weiyi=false;
	return re;
}
void deal()
{
	int count,sum=0;
	weiyi=true;
	result=0;
	for(count=1;count<=n;count++) {dus[count]=du[count];used[count]=false;}
	while(1)
	{
		//testout();
		int temp=pick();
		//cout<<temp<<endl;
		if(temp==0) break;
		sum++;
		used[temp]=true;
		outline[sum]=temp;
		for(count=1;count<=n;count++)
			dus[count]-=map[temp][count];
	}
//	cout<<sum<<endl;
	if(sum<n) result=-1;
	else if(weiyi==true) result=1;
	//cout<<endl;
}
void out()
{
	int i;
	for(i=1;i<=n;i++)
	{
		cout<<char(outline[i]+'A'-1);
	}
}
int main()
{
	while(cin>>n>>m,n)
	{
		//cout<<n<<m<<endl;
		int i,j,count;
		for(i=1;i<=n;i++)
		{
			du[i]=0;
			for(j=1;j<=n;j++)
			{
				map[i][j]=0;
			}
		}
		done=false;
		for(count=1;count<=m;count++)
		{
			cin>>input;
			if(done) continue;
			int u,v;
			u=input[0]-'A'+1;
			v=input[2]-'A'+1;
			map[u][v]++;
			du[v]++;
			deal();
			if(result==1) {done=true;cout<<"Sorted sequence determined after "<<count<<" relations: ";out();cout<<".\n";}
			if(result==-1) {done=true;cout<<"Inconsistency found after "<<count<<" relations."<<endl;}
		}
		if(!done) cout<<"Sorted sequence cannot be determined."<<endl;
	}
	return 0;
}