#include<iostream>
using namespace std;
#define M 26
bool grap[M+1][M+1];
int squ[M+1];
char equ[M*M][4];
int ind[M+1];
int indcop[M+1];
int cnt,n,m;
int topsort()
{
int i,j,p,num=0,
flag=0,
now=0;
for(i=0;i<n;i++)
indcop[i]=ind[i];
for(i=0;i<n;i++)
{
num=0;
for(j=0;j<n;j++)
if(indcop[j]==0)
{
num++;
p=j;
}
if(num==0) //有回路
return 0;
if(num>1) //不確定
flag=1;
//return -1; //不確定的情況下還要判斷有沒回路，o(╯□╰)o
indcop[p]=-1; //置為負值
squ[now++]=p;
for(j=0;j<n;j++) //刪除相關的邊
if(grap[p][j])
indcop[j]--;
}
if(flag) return -1; //不確定
return 1;
}
int main()
{
int i,j,ret;
char l,r;
bool done;
while(scanf("%d%d",&n,&m)==2 && n )
{
for(i=0;i<m;i++)
scanf(" %s",&equ[i]);
done=false;
memset(ind,0,sizeof(ind));
memset(grap,0,sizeof(grap));
for(i=0;i<m;i++)
{
l=equ[i][0];r=equ[i][2];
grap[l-'A'][r-'A']=true;
ind[r-'A']++;
ret=topsort();
if( ret==0 ) { printf("Inconsistency found after %d relations.\n",i+1); done=true; break;}
if( ret==1)
{
printf("Sorted sequence determined after %d relations: ",i+1);
for(j=0;j<n;j++)
printf("%c",'A'+squ[j]);
printf(".\n");
done=true;
break;
}
}
if(!done) printf("Sorted sequence cannot be determined.\n");
}
return 0;
}posted on 2009-07-13 14:00
wyiu 閱讀(200)
評論(0) 編輯 收藏 引用 所屬分類:
POJ