4676085_wa.cpp

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

#include<iostream>
using namespace std;
int n,m;
int map[28][28];
int du[28],dus[28];
bool used[28];
char input[10];
int result;
int outline[28];
bool done;
int pick()
{
	int sum=0,re=0;
	for(int count=1;count<=n;count++)
	{
		if(dus[count]==0&&used[count]==false) 
		{
			re=count;
			sum++;
			if(sum==2){return 0;}
		}
	}
	if(sum==0) return -1;
	else return re;
}
void deal()
{
	int count;
	for(count=1;count<=n;count++)
	{
		dus[count]=du[count];
		used[count]=false;
	}
	for(count=1;count<=n;count++)
	{
		int temp=pick();
		if(temp==-1) {result=-1;return;}
		if(temp==0) {result=0;return;}
		used[temp]=true;
		for(int i=1;i<=n;i++)
		{
			dus[i]-=map[temp][i];
		}
		outline[count]=temp;
	}
	result=1;
}
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;
}