拓扑排序POJ 1094

这题就是拓扑排序，但是能确定的情形必须是拓扑序列唯一。做法是在读边的时候，读完一条边后就调用topsort函数，如果通过topsort函数能确定出现环，则矛盾，或者存在了把所有 n个字母都包括进去了的唯一拓扑序列。就可以输出结果，以后就不调用topsort函数了。但是注意剩下的数据要读完，当读完所有的边上述两种情况都还没有出现，就可以输出不能确定了

我是这样做的，在做拓扑排序时，先把入度为0的顶点入栈，该顶点入度设为-1（这样就不会重复入栈）如果出现两入度为0，可以知道不存在唯一拓扑序列了，别急，要接着做拓扑排序，从栈中 pop出元素，所有是该顶点后继的顶点的入度减一，再找入度为0的顶点入栈，直至栈空，判断会不会出现环，排除出现矛盾的情形，这样才不遗漏啊````

这题让我很无语，一直WA，本来我是自己手打的那什么Sorted sequence blabla一长串，想试试自己会不会打错，事实上，我一个一个的比对了，自我感觉没什么错的地方啊，连空格都认真看了，然后我修改了一下程序，再复制粘贴原网页上语句的又交了一次，然后就A了，事实证明，自己打也许真的很坑爹啊。。。。。

下面贴代码：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 int n,m;
  4 int sn ;  //关系描述中出现过多少不同字母
  5 char l[30];
  6 struct  node//顶点
  7 {
  8     int num; //出边数目
  9     int count; //入度，当入过栈后，入度为-1
 10     int temp;  //用来坐复制板
 11     int edge[50]; //出边的终点
 12     bool visited; //顶点是否是出现关系描述中
 13 } p[30];
 14 int Topsort()
 15 {
 16     int mystack[30];
 17     bool ist = true ;
 18     int cur = 0;
 19     int cnt = 0;
 20     int re = 0;//同时出现两个入度为0也算是不确定的
 21     for(int k = 0; k<n; k++)
 22         p[k].temp = p[k].count;
 23     for(int i=0; i< n; i++)
 24     {
 25         if(p[i].visited && p[i].temp==0)
 26         {
 27             mystack[cur++] = i;
 28             l[ cnt++] = i+'A';
 29             p[i].temp--;
 30             re++;
 31         }
 32     }
 33     if(re > 1) ist = false;
 34     while(cur != 0)
 35     {
 36         cur--;
 37         int t = mystack[cur];
 38         for(int j = 0; j< p[t].num; j++)
 39             p[p[t].edge[j]].temp--;
 40         re = 0;
 41         for(int i=0; i< n; i++)
 42         {
 43             if(p[i].visited && p[i].temp == 0)
 44             {
 45                 mystack[cur++] = i;
 46                 l[cnt++] = i+'A';
 47                 p[i].temp--;
 48                 re++;
 49             }
 50         }
 51         if(re > 1) ist = false;
 52     }
 53     l[cnt] = '\0';
 54     if(cnt < sn) return 2; //出现矛盾
 55     else if(cnt < n || !ist) return 0; //表示不确定
 56     else if(cnt == n ) return 1;//可以确定拓扑排序
 57 }
 58 int main()
 59 {
 60 //    freopen("in1.cpp","r",stdin);
 61     while(~scanf("%d%d",&n,&m))
 62     {
 63         bool flag = false;  //有确定结果了
 64         if(n== 0 && m == 0) break;
 65         for(int i=0; i<n; i++)
 66         {
 67             p[i].temp = 0;
 68             p[i].count = 0;
 69             p[i].num = 0;
 70             p[i].visited = false;
 71         }
 72         sn = 0;
 73         for(int i=0; i<m; i++)
 74         {
 75             char a[5];
 76             scanf("%s",a);
 77             if(!flag)
 78             {
 79                 int u = a[0] - 'A';
 80                 int v = a[2] - 'A';
 81                 p[u].edge[p[u].num++] = v;
 82                 p[v].count++;
 83                 if(!p[u].visited)
 84                 {
 85                     p[u].visited = true;
 86                     sn++;
 87                 }
 88                 if(!p[v].visited)
 89                 {
 90                     p[v].visited = true;
 91                     sn++;
 92                 }
 93                 int der = Topsort();
 94                 if(der == 2)
 95                 {
 96                     printf("Inconsistency found after %d relations.\n",i+1);
 97                     flag = true;
 98                 }
 99                 else if(der == 1 )
100                 {
101                     printf("Sorted sequence determined after %d relations: %s.\n",i+1,l);
102                     flag = true;
103                 }
104             }
105         }
106         if(!flag) printf("Sorted sequence cannot be determined.\n");
107     }
108     return 0;
109 }