拓扑排序

 #include <iostream>
using namespace std;
int n,m,cnt[27],sum[27],map[27][27],pr[27];
char str[5];
int toposoft()
{
 int i,j,num,now,s,flag;
 now=flag=0;////////////////!!!
 memset(pr,0,sizeof(pr));
 for(i=1;i<=n;i )
  cnt[i]=sum[i];///////////用CNT记录，免得修改了sum数组的值;
 for(i=1;i<=n;i )
 {
  num=0;////////!!!!!!!!!!!!!
  for(j=1;j<=n;j )
   if(cnt[j]==0)////////查找入度为0的点，记录入度为0的点;
   {
    num ;
    s=j;
   }
  if(num==0)
   return 0;/////////////入度为0的点一个都没有;
  if(num>1)//////////当入度为0的点只有一个是，该序列才有顺序;
   flag=1;
  pr[now ]=s;///入列
  cnt[s]=-1;//////////已经入列的点标记;
  for(j=1;j<=n;j )
   if(map[s][j]==1)
    cnt[j]--;///////////////删除边;
 }
 if(flag)
  return -1;
 return 1;

}
int main()
{
 while(1)
 {
  scanf("%d%d",&n,&m);
  if(n==0&&m==0)
   break;
  memset(map,0,sizeof(map));
  memset(sum,0,sizeof(sum));
  memset(cnt,0,sizeof(cnt));
  int sign=0,i;
  for(i=1;i<=m;i )
  {
   cin>>str;///////////////!!!!
   if(sign)
    continue;///////////////!!!
   int u=str[0]-'A' 1;
   int v=str[2]-'A' 1;
   map[u][v]=1;
   sum[v] ;
   int ans=toposoft();
   if(ans==0)
   {
    printf("Inconsistency found after %d relations./n",i);
    sign=1;
   }
   if(ans==1)
   {
    printf("Sorted sequence determined after %d relations: ",i);
    for(int j=0;j<n;j )
     putchar(pr[j] 'A'-1);
    printf("./n");
    sign=1;
   }
  }
  if(!sign)
   printf("Sorted sequence cannot be determined./n");
  }

 return 0;
}