前置知识:拓扑排序

详细注释都在代码里

 1 //该题题意明确,就是给定一组字母的大小关系判断他们是否能组成唯一的拓扑序列。
 2 //是典型的拓扑排序,但输出格式上确有三种形式:
 3
 4 //   1.该字母序列有序,并依次输出;
 5
 6 //   2.该序列不能判断是否有序;
 7
 8 //   3.该序列字母次序之间有矛盾,即有环存在。
 9
10 //     而这三种形式的判断是有顺序的:先判断是否有环(3),
11 //再判断是否有序(1),最后才能判断是否能得出结果(2)。
12 //注意:对于(2)必须遍历完整个图,而(1)和(3)一旦得出结果,
13 //对后面的输入就不用做处理了。
14
15 //有一个问题,我不太清楚,就是在确定有序之后,就直接输出答案,
16 //对右面的输入也不再处理,但是后面的输入可以让其成为环的话又就会
17 //让其成为环,所以我想这道题就是在确定有序之后,后面的数据,就都不要了。
18 //应该是这意思把
19 #include<cstdio>
20 #include<algorithm>
21 #include<string.h>
22 #include<math.h>
23 #include<queue>
24 using namespace std;
25 typedef long long ll;
26 const int maxn=1e2+10;
27 int G[30][30];
28 int in[30];
29 int q[30];
30 void init()
31 {
32     memset(G,0,sizeof(G));  //
33     memset(in,0,sizeof(in));  //入度
34 }
35 int Toposort(int n)
36 {
37     int aim;int cot=0;
38     int tmpin[30];
39     int flag=1;  //1的时候表示有序
40     for(int i=1;i<=n;i++) tmpin[i]=in[i];  //将入度复制到tmpin里面来
41     for(int i=1;i<=n;i++){
42         int num=0;
43         for(int j=1;j<=n;j++)
44             if(!tmpin[j]) num++,aim=j;  //这里来判断入度数量,aim是入度为0的那个点
45             //这里如果出现多个入度,就会选择最后面那个先进行操作;
46         if(!num) return 0;  //有环;
47         if(num>1) flag=-1; //无序
48         q[cot++]=aim;
49         tmpin[aim]=-1;
50         for(int j=1;j<=n;j++)
51             if(G[aim][j]) tmpin[j]--;
52     }
53     return flag;
54
55 }
56 int main()
57 {
58     int n,m;
59     while(scanf("%d%d",&n,&m)!=EOF){
60         if(!n&&!m) break;
61         init();
62         char str[5];
63         int flag=0;
64         for(int i=1;i<=m;i++){
65             scanf("%s",str);
66             if(flag) continue;
67             int l=str[0]-'A'+1;
68             int r=str[2]-'A'+1;
69             G[l][r]=1;
70             in[r]++;
71             int judge=Toposort(n);
72             //有环
73             if(!judge) printf("Inconsistency found after %d relations.\n",i),flag=1;
74             if(judge==1){  //有序
75                 printf("Sorted sequence determined after %d relations: ",i);
76                 for(int j=0;j<n;j++)
77                     printf("%c",q[j]+'A'-1);
78                 printf(".\n");
79                 flag=1;
80             }
81         }
82         //无序
83         if(!flag) printf("Sorted sequence cannot be determined.\n");
84     }
85     return 0;
86 }
01-03 06:49