poj1094Sorting It All Out（拓扑排序）

http://poj.org/problem?id=1094

1A 这题下午想了好久一直没调出来由于是边输入边拓扑排序入度改变之后下次再排会出错晚上回来想到这一点每次全复制一遍只对入度进行操作不进行改变

这个题要判断三种情况

一种是有环在给出几种关系时出现矛盾

二是在给出几种关系时 n个数已经排好了序

三是输完还是无法排出一种序这是属于拓扑排序不唯一的情况也就是同时有多个结点出现的入度为0

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 int f[100],g[50][50],kk[30],q[50];
  4 int topo(int n,int m)
  5 {
  6     int i,j,f2 = 0,f1=0,x,dd[50],d,y = 0;
  7     for(i = 1; i <= n ; i++)
  8         dd[q[i]] = f[q[i]];
  9     for(i = 1; i <= n ; i++)
 10     {
 11         f1 = 0;
 12         for(j = 1; j <= n ; j++)
 13         {            
 14             if(dd[q[j]]== 0)
 15             {
 16                 f1 ++;
 17                 d = q[j];
 18             }                                
 19         }
 20         if(f1)
 21         {
 22             f2++;
 23             if(f1>1)
 24             y = 1;
 25             dd[d] = -1;
 26             kk[f2] = d;
 27             for(x = 1; x <= n ; x++)
 28                 if(g[d][q[x]])
 29                     dd[q[x]]--;
 30         }
 31         else
 32             break;
 33     }
 34     if(f2<n)
 35     return 0;
 36     else
 37     if(f2==m&&!y)
 38     return 1;
 39     else
 40     return 2;
 41 }
 42 int main()
 43 {
 44     int i,j,k,n,m,w[28],x;
 45     char c1,c2;
 46     while(scanf("%d%d", &n,&m)&&n&&m)
 47     {
 48         int h1=0,h2 =0;
 49         int d = 0;
 50         memset(w,0,sizeof(w));
 51         memset(f,0,sizeof(f));
 52         memset(g,0,sizeof(g));
 53         for(i = 1; i <= m ; i++)
 54         {
 55             scanf("%*c%c%*c%c",&c1,&c2);
 56             if(!w[c1-'A'])
 57             {
 58                 d++;
 59                 q[d] = c1-'A';
 60                 w[c1-'A'] = 1;
 61             }
 62             if(!w[c2-'A'])
 63             {
 64                 d++;
 65                 q[d] = c2-'A';
 66                 w[c2-'A'] = 1;
 67             }
 68             if(!g[c1-'A'][c2-'A'])
 69             {
 70                 g[c1-'A'][c2-'A']= 1;
 71                 f[c2-'A']++;
 72             }
 73             if(!h1&&!h2)
 74             {
 75                 int mm = topo(d,n);
 76                 if(mm==1)
 77                 {
 78                     x  = i;
 79                     h1 = 1;
 80                 }
 81                 if(!mm)
 82                 {
 83                     x = i;
 84                     h2 = 1;
 85                 }
 86             }
 87         }
 88         if(h1)
 89         {
 90             printf("Sorted sequence determined after %d relations: ",x);
 91             for(i = 1; i <= n ; i++)
 92                 printf("%c",kk[i]+'A');
 93             printf(".\n");
 94         }
 95         if(h2)
 96         {
 97             printf("Inconsistency found after %d relations.\n",x);
 98         }
 99         if(!h1&&!h2)
100             printf("Sorted sequence cannot be determined.\n");
101     }
102     return 0;
103 }