poj 1094 Sorting It All Out(拓扑排序)-白红宇

poj 1094 Sorting It All Out(拓扑排序)

阅读量：4606 次

发布时间：2019-06-09

本文共 1223 字，大约阅读时间需要 4 分钟。

题目：

题意：给定一个关系，判断三种情况

1、到第几组的时候就可以判断出什么关系了

2、到第几组的时候可以判断矛盾

3、判断不出来

每次输入，都要拓扑判断

1 #include 
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 using namespace std;10 11 int flag,dis[30],cnt;12 int n,G[100][100],r[30];13 char f[300];14 void find()15 {16 int i,j,k,count,x;17 flag=1; //一直为1 的话说明 判断出关系了18 cnt=0;21 memcpy(dis,r,n*sizeof(int));22 for(i=0; i
             
              1) //说明现在还没判断出关系来39 flag = -1;40 dis[x] = -1;41 f[cnt++]=x+65;42 for(j=0; j
              
               >n>>m&&(m!=0||n!=0))55 {56 getchar();57 flag = 0; cnt=0;58 memset(r,0,sizeof(r));59 memset(G,0,sizeof(G));60 for(k=1; k<=m; k++)61 {62 x=0;63 scanf("%c%c%c",&a,&b,&c);64 getchar();65 if(flag)66 continue;67 if(G[a-65][c-65]==0)68 {69 G[a-65][c-65]=1;70 r[c-65]++;71 }72 find();73 switch(flag)74 {75 case -1:flag=0; break;76 case 0: flag=1; printf("Inconsistency found after %d relations.\n",k); break;77 case 1: f[cnt]='\0'; printf("Sorted sequence determined after %d relations: %s.\n",k,f); break;78 }79 }80 if(!flag)81 printf("Sorted sequence cannot be determined.\n");82 }83 return 0;84 }