poj1094——Sorting It All Out
拓扑排序！具体方法见：http://www.cnblogs.com/xiaosuo/archive/2010/03/26/1690302.html#include<stdio.h>#include<string.h>struct node{ int u,v;}tt;int n,m,k,dgree,queue,rear,front;bool flag,flag1,edge,vis;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.u].v]){edge.u].v]=false;dgree.v]+=1;}}for(i=1;i<=n;i++)if(dgree==0){queue[++rear]=i;vis=false;}if(rear>1)equal=false;memset(edge,true,sizeof(edge));while(rear!=front){front++;;for(i=1;i<=k;i++){if(tt.u==queue&&edge.u].v]){edge.u].v]=false;dgree.v]--;}}for(i=1;i<=n;i++)if(dgree==0&&vis){vis=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-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;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.u=p-'A'+1;tt.v=p-'A'+1;}for(k=1;k<=m;k++){if(flag1)NPFTP();}if(flag)printf("Sorted sequence cannot be determined.\n");}return 0;}
页:
[1]