poj1094——Sorting It All Out

44424742

拓扑排序！具体方法见：http://www.cnblogs.com/xiaosuo/archive/2010/03/26/1690302.html
#include<stdio.h>#include<string.h>struct node{   int u,v;}tt[1000];int n,m,k,dgree[27],queue[1000],rear,front;bool flag,flag1,edge[27][27],vis[27];void NPFTP(){int i;bool equal=true;rear=0;front=0;memset(edge,true,sizeof(edge));memset(dgree,0,sizeof(dgree));memset(vis,true,sizeof(vis));for(i=1;i<=k;i++){if(edge[tt[i].u][tt[i].v]){edge[tt[i].u][tt[i].v]=false;dgree[tt[i].v]+=1;}}for(i=1;i<=n;i++)if(dgree[i]==0){queue[++rear]=i;vis[i]=false;}if(rear>1)equal=false;memset(edge,true,sizeof(edge));while(rear!=front){front++;;for(i=1;i<=k;i++){if(tt[i].u==queue[front]&&edge[tt[i].u][tt[i].v]){edge[tt[i].u][tt[i].v]=false;dgree[tt[i].v]--;}}for(i=1;i<=n;i++)if(dgree[i]==0&&vis[i]){vis[i]=false;queue[++rear]=i;}if(rear-front>1)equal=false;}if(rear==n&&equal){flag1=false;flag=false;printf("Sorted sequence determined after %d relations: ",k);    for(i=1;i<=rear;i++)printf("%c",queue[i]-1+'A');printf(".\n");}else if(rear<n){flag1=false;flag=false;printf("Inconsistency found after %d relations.\n",k);}}int main(){int i,j;char p[5];while(scanf("%d%d",&n,&m)!=EOF){flag=true;flag1=true;if(n==0&&m==0)break;for(k=1;k<=m;k++){scanf("%s",&p);tt[k].u=p[0]-'A'+1;tt[k].v=p[2]-'A'+1;}for(k=1;k<=m;k++){if(flag1)NPFTP();}if(flag)printf("Sorted sequence cannot be determined.\n");}return 0;}