1 #include <cstdio>
2 #include <memory>
3 const int MAXN = 27 ;
4 const int SIZE = 501 ;
5
6 struct NODE
7 {
8 int ID ;
9 NODE *next ;
10 };
11
12 NODE edge[MAXN] , g_Temp[SIZE] ;
13 int g_Pos ;
14
15 int num , n , gm ;
16 int degree[MAXN] ;
17 char seq[MAXN] ;
18 bool visited[MAXN] ;
19
20 //拓撲排序
21 int TopSort(const int& NodeNum)
22 {
23 int Stack[MAXN] , top = -1 , i , flag , temp[MAXN] ;
24 NODE *ptr = NULL ;
25
26 flag = -2 ;
27 gm = 0 ;
28 //先找出初始狀態(tài)下入度為0的點
29 //如果有多個點則標志為-1
30 for ( i = 0 ; i < MAXN ; ++i )
31 {
32 temp[i] = degree[i] ;
33 if ( degree[i] == 0 && visited[i])
34 {
35 Stack[++top] = i ;
36 if ( top > 0 )
37 flag = -1 ;
38 }
39 }
40 //記錄序列，并判斷是否有多個解存在
41 while ( top != -1 )
42 {
43 seq[gm++] = (char)(Stack[top] + 'A') ;
44 ptr = edge[Stack[top--]].next ;
45
46 while (ptr)
47 {
48 temp[ptr->ID]-- ;
49
50 if ( temp[ptr->ID] == 0 )
51 {
52 Stack[++top] = ptr->ID ;
53 if ( top > 0 ){
54 flag = -1 ;
55 }
56 }
57
58 ptr = ptr->next ;
59 }
60 }
61 //如果有環(huán)存在，則返回0
62 if ( gm < NodeNum )
63 return 0 ;
64 //如果能確定序列，則返回1
65 if ( gm == num && flag != -1 )
66 flag = 1 ;
67
68 return flag ;
69 }
70
71 void Insert( const int& x , const int& y )
72 {
73 NODE *tmp = &g_Temp[g_Pos++] ;
74 tmp->ID = y ;
75 tmp->next = edge[x].next ;
76 edge[x].next = tmp ;
77 }
78
79 void Init()
80 {
81 int i ;
82 for ( i = 0 ; i < MAXN ; ++i )
83 {
84 degree[i] = 0 ;
85 visited[i] = false ;
86 edge[i].next = NULL ;
87 }
88
89 g_Pos = 0 ;
90 gm = 0 ;
91 }
92 int main()
93 {
94 // freopen("in", "r", stdin ) ;
95 char inStr[5];
96 int i , ia , ic , cnt , flag , ans ;
97 bool circle ; //標志是否有環(huán)
98
99 while ( 1 )
100 {
101 scanf("%d %d", &num, &n) ;
102 if ( num == 0 || n == 0 )
103 break ;
104
105 Init() ;
106 cnt = 0 ;
107 ans = 1000 ; //由于沒有輸入過程中輸出答案，所以需要加些標記
108 flag = -2 ;
109 circle = false ;
110 for ( i = 1 ; i <= n ; ++i )
111 {
112 scanf("%s", &inStr) ;
113
114 ia = inStr[0] - 'A' , ic = inStr[2] - 'A' ;
115
116 degree[ic]++ ;
117
118 if ( !visited[ia] ){
119 visited[ia] = true ;
120 cnt++ ;
121 }
122 if ( !visited[ic] ){
123 visited[ic] = true ;
124 cnt++ ;
125 }
126
127 Insert( ia, ic ) ;
128
129 if ( flag != 1 )
130 {
131 flag = TopSort( cnt ) ;
132 if ( flag == 0 && ans > i )
133 {
134 ans = i ;
135 circle = true ;
136 }
137 else if ( flag == 1 )
138 {
139 ans = i ;
140 }
141 }
142 }
143 //先確定有解
144 if ( flag == 1 )
145 {
146 seq[gm] = 0 ;
147 printf("Sorted sequence determined after %d relations: %s.\n", ans, seq) ;
148 }
149 else if ( circle )//在確定有環(huán)
150 {
151 printf("Inconsistency found after %d relations.\n", ans) ;
152 }
153 else {
154 printf("Sorted sequence cannot be determined.\n") ;
155 }
156
157 }
158 return 0 ;
159 }
160