拓扑排序（poj 1094)

前置知识：拓扑排序

详细注释都在代码里

 //该题题意明确，就是给定一组字母的大小关系判断他们是否能组成唯一的拓扑序列。

 //是典型的拓扑排序，但输出格式上确有三种形式：

 //   1.该字母序列有序，并依次输出；

 //   2.该序列不能判断是否有序；

 //   3.该序列字母次序之间有矛盾，即有环存在。

 //     而这三种形式的判断是有顺序的：先判断是否有环（3），

 //再判断是否有序（1），最后才能判断是否能得出结果（2）。

 //注意：对于（2）必须遍历完整个图，而（1）和（3）一旦得出结果，

 //对后面的输入就不用做处理了。

 //有一个问题，我不太清楚，就是在确定有序之后，就直接输出答案，

 //对右面的输入也不再处理，但是后面的输入可以让其成为环的话又就会

 //让其成为环，所以我想这道题就是在确定有序之后，后面的数据，就都不要了。

 //应该是这意思把

 #include<cstdio>

 #include<algorithm>

 #include<string.h>

 #include<math.h>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int maxn=1e2+;

 int G[][];

 int in[];

 int q[];

 void init()

 {

     memset(G,,sizeof(G));  //图

     memset(in,,sizeof(in));  //入度

 }

 int Toposort(int n)

 {

     int aim;int cot=;

     int tmpin[];

     int flag=;  //1的时候表示有序

     for(int i=;i<=n;i++) tmpin[i]=in[i];  //将入度复制到tmpin里面来

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

         int num=;

         for(int j=;j<=n;j++)

             if(!tmpin[j]) num++,aim=j;  //这里来判断入度数量，aim是入度为0的那个点

             //这里如果出现多个入度，就会选择最后面那个先进行操作；

         if(!num) return ;  //有环；

         if(num>) flag=-; //无序

         q[cot++]=aim;

         tmpin[aim]=-;

         for(int j=;j<=n;j++)

             if(G[aim][j]) tmpin[j]--;

     }

     return flag;

 }

 int main()

 {

     int n,m;

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

         if(!n&&!m) break;

         init();

         char str[];

         int flag=;

         for(int i=;i<=m;i++){

             scanf("%s",str);

             if(flag) continue;

             int l=str[]-'A'+;

             int r=str[]-'A'+;

             G[l][r]=;

             in[r]++;

             int judge=Toposort(n);

             //有环

             if(!judge) printf("Inconsistency found after %d relations.\n",i),flag=;

             if(judge==){  //有序

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

                 for(int j=;j<n;j++)

                     printf("%c",q[j]+'A'-);

                 printf(".\n");

                 flag=;

             }

         }

         //无序

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

     }

     return ;

 }