poj1094Sorting It All Out 拓扑排序

　　做拓扑排序的题目，首先要知道两条定理：

　　　　1、最后得到的拓扑数组的元素个数如果小于n，则不存在拓扑序列。（有圈）

　　　　2、如果一次入队的入度为零的点数大于1，则拓扑序列不唯一。　　（关系不确定）

　　本题有一个默认的东西，如果到了第K（看K<m）步，能唯一确定一个序列，就不用管之后会不会产生矛盾。

　　这题的思路还是比较清晰的。输入也只有X<Y(只有<符号，并且X，Y都只是大写字母)，数据量比较小。不过边数没有限制，用链式前向星的话不太好，还是用邻接矩阵吧。每次用邻接矩阵要注意的是判断重边，做小生成树的时候是用初始化边为无穷大，然后每次取小的。但是这里没有边权，所以只要有边，赋值为1，就可以了。遇到重边的话，不能再加入度。

　　只需要拓扑排序就可以解决这个问题了。我就犯了画蛇添足的错误，我居然用floyd去判圈。这主要是对拓扑排序理解不够的原因。当出现的字母的数字小于n时，没出现的字母的入度是零，所以不影响拓扑排序产生的数据元素的个数。只有有圈的情况才会使得数组元素个数小于n。

　　还有，我犯了一个很二的错误。因为没输入一组数据就要做一次拓扑排序。我居然把统计入度的数组没有变化就用了。囧了。再声明一个数组，每次拓扑排序之前，把入度数组的数据复制过来就好了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int N = ;

 int ind[N],que[N], g[N][N],id[N];

 int iq,flag, T;

 void topo(int n)

 {

     int i,k,j=,x;

     T=;

     for(i=;i<=n;i++)

     {

         id[i]=ind[i];

         if(id[i]==) que[j++]=i;

     }

     if(j>) T=;

     x=j;

     for(i=;i<j;i++)

     {

         if(j-x>) T=;

         x=j;

         int u=que[i];

         for(k=;k<=n;k++)

         {

             if(g[u][k]&&u!=k)

             {

                 id[k]--;

                 if(id[k]==) que[j++]=k;

             }

         }

     }

     iq=j;

 }

 void init()

 {

     flag=;

     memset(ind,,sizeof(ind));

     memset(g,,sizeof(g));

 }

 int main()

 {

     //freopen("test.txt","r",stdin);

     int n,m,i,j,k,t,a,b;

     char ch1,ch2,ch;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         if(!n) break;

         init();

         t=;

         for(k=;k<=m;k++)

         {

             do

                 scanf("%c",&ch1);

             while (!isalpha(ch1)) ;

             scanf("<%c",&ch2);

             if(flag) continue;

             a=ch1-,b=ch2-;

             if(a>n||b>n||a==b) flag=;

             if(flag) {printf("Inconsistency found after %d relations.\n",k);continue;}

             if(g[a][b]) continue;

             g[a][b]=;

             ind[b]++;

             topo(n);

             if(iq<n){flag=;printf("Inconsistency found after %d relations.\n",k);continue;}

             if(iq==n&&!T){

                 flag=;

                 printf("Sorted sequence determined after %d relations: ",k);

                 for(i=;i<n;i++) printf("%c",que[i]+);

                 printf(".\n");

                 continue;

             }

             if(k==m&&!flag) printf("Sorted sequence cannot be determined.\n");

         }

     }

     return ;

 }

巴特西

poj1094Sorting It All Out 拓扑排序

最新文章

热门文章