好久没写程序练手了，今天本来准备拿POJ1025开刀的，但是1025这个模拟题目太
繁杂了，换一个，写POJ1094，结果郁闷地写了三个多小时——代码水平有待提升呀。
下面是我写这个题目的详细过程，跟大家分享下：
题目地址：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1094题目描述：
一个升序串是一群用小于号连接起来的由小到大排列好的数值。例如，一个排好的序列 A, B, C, D 就表示 A < B, B < C 还有 C < D。现在，给你一堆格式为 A < B 的关系式给你，然后你就要去判断有没有一个可以排列的顺序。
Input
输入数据由多组测试数据组成。每一组测试数据的第一行是两个整数n 和 m。 第一个整数代表有多少个字母要排列，而且 2 <= n <= 26。要排列的字母是大写字母中的前n个。 第二个整数m表示会出现多少组像 A < B 这样的数值关系。下面的m行，每一行有一个只有三个字符的关系式：一个大写字母，符号“<”和另一个大写字母。除了前n个大写字母以外，不会其他字母字母。当 n = m = 0 时表示输入结束。
Output
对应每组输入数据，输出只有一行。这一行要是以下三种情况之一：
Sorted sequence determined after xxx relations: yyy…y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
xxx 就是当一个升序序列确定时或者发现有矛盾时所处理到的第几个关系式，哪种情况先出现，就输出哪种；而 yyy…y 就是排好序的升序序列。
××××××××××××××××××××××××××××××××××××××××××××××××××××××
下面是正题：
我拿到题目就认为这个题目的算法很简单——不就拓扑排序嘛。但有一点比较关键：需要每输入一个关系就判断一次。不过总共的元素最多才26个，时间应该是够用的。
然后就写，很快写完，过了样例，检查了一下，提交，WA,
两个错误原因，一个是一条语句（见下面注释）。
一个是没有判断环。
然后我就用DFS判断环。
第二次得到TLE。
后面想了下DFS太慢，改进用矩阵判断是否有回路。
第三次得到WA。.
然后重写，还是WA。怎么回事？
然后看Discuss吧。
发现一组数据过不了
11 12
K<J
B<A
E<F
D<F
G<F
H<I
G<E
I<K
J<F
A<H
F<C
C<B
原来是矩阵更新写错了，再写再交……
呜呜呜，这回还是WA.
原来太急躁了，样例都没过——我把矩阵与元素之间得关系弄一起了，郁闷了。
然后再改吧。
这回没有过，我还是发现了错误，
1 0
这一组都过不了。
改了再交，就是WA!!!???
终于找到了一句，每次排序后把元素的入度改了，
改好后交，还是WA.
原来没有删掉测试数据。
删掉测试数据，终于AC了。
总结：
最后算法跟开始想的方向一样，主要是具体实现有问题——而且都是细节，主要反映在对数据挖掘得不够上。
自己很久没写代码解题了，更加久没写图论的题目了，现在考试只剩下专业课了，我可以适当放手开始写代码了——手生得厉害，我毕竟跟那些过分注重成绩的人不是一样的，还是做自己喜欢的事吧。
下面是代码（很乱，加了我写代码的一系列过程中的调试注释）：
1 /*********************************************************************
2 Author: littlekid
3 Created Time: 2008-1-11 11:49:58
4 Problem Source: POJ1094
5 Description:
6 第一次WA,两个错误原因，一个是一条语句（见下面注释）。
7 一个是没有判断环。
8
9 用DFS判断环。
10 第二次得到TLE。
11
12 后改进用矩阵判断是否有回路。
13 第三次得到WA.
14
15 然后重写，还是WA。怎么回事？
16 然后看Discuss吧。
17 发现一组数据过不了
18 11 12
19 K<J
20 B<A
21 E<F
22 D<F
23 G<F
24 H<I
25 G<E
26 I<K
27 J<F
28 A<H
29 F<C
30 C<B
31
32 原来是矩阵更新写错了，再写再交……
33 呜呜呜，这回还是WA.
34
35 原来太急躁了，样例都没过——我把矩阵与元素之间得关系弄一起了，郁闷了。
36 然后再改吧。
37
38 这回没有过，我还是发现了错误，
39 1 0
40 这一组都过不了。
41
42 改了再交，就是WA!!!???
43
44 终于找到了一句，每次排序后把元素的入度改了，
45 改好后交，还是WA.
46 原来没有删掉测试数据。
47 ********************************************************************/
48
49 # include <iostream>
50 using namespace std;
51
52 const bool NOT_DETERMINE = true;
53 const bool FIND_INCONSISTENCY = true;
54
55 typedef struct node{
56 int in_degree;
57 int out_degree;
58 int out[ 27 ];
59 };
60
61 node elem[ 27 ];
62 int sequence[ 27 ];
63
64 int relation[ 27 ][ 27 ];
65
66 void test( int n )
67 {
68 for ( int i = 0; i < n; i ++ )
69 {
70 for ( int j = 0; j < n; j ++ )
71 {
72 printf( "%d ", relation[ i ][ j ] );
73 }
74 printf( "\n" );
75 }
76 }
77
78 void output( bool flag )
79 {
80 printf( "Sorted sequence cannot be determined.\n" );
81 }
82
83 void output( bool flag, int no )
84 {
85 printf( "Inconsistency found after %d relations.\n", no );
86 }
87
88 void output_relation_ship( int n )
89 {
90 for ( int i = 0; i < n; i ++ )
91 {
92 printf( "%c", sequence[ i ]+'A' );
93 }
94 }
95
96 void output( int no, int n )
97 {
98 printf( "Sorted sequence determined after %d relations: ", no );
99 output_relation_ship( n );
100 printf( ".\n" );
101 }
102
103 void add_relation_ship( int a, int b, int n )
104 {
105 //elem[ a ].out_degree ++;//The first edition come up WA because of this sentence
106 elem[ b ].in_degree ++;
107
108 elem[ a ].out[ elem[ a ].out_degree ++ ] = b;
109
110 relation[ a ][ b ] = 1;
111 for ( int i = 0; i < n; i ++ ) ///
112 {
113 for ( int j = 0; j < n; j ++ )
114 {
115 for ( int k = 0; k < n; k ++ )
116 {
117 if ( relation[ i ][ k ] && relation[ k ][ j ] )
118 {
119 relation[ i ][ j ] = 1;
120 }
121 }
122 }
123 }
124 }
125 /*
126 bool have_visited[ 27 ];
127 int color[ 27 ];
128
129 int DFS( int now )
130 {
131 if ( have_visited[ now ] )
132 {
133 return 1;
134 }
135 have_visited[ now ] = true;
136 color[ now ] = 1;
137 for ( int i = 0; i < elem[ now ].out_degree; i ++ )
138 {
139 if ( DFS( elem[ now ].out[ i ] ) == 1 ) return 1;
140 }
141 have_visited[ now ] = false;
142 return 0;
143 }
144
145
146 int has_circle( int n )
147 {
148 memset( color, 0, sizeof( color ));
149 memset( have_visited, false, sizeof( have_visited ) );
150 for ( int i = 0; i < n; i ++ )
151 {
152 if ( !color[ i ] )
153 if ( DFS( i ) == 1 ) return -1;
154 }
155 return 0;
156 }
157 */
158
159 int has_circle( int n )
160 {
161 for ( int i = 0; i < n; i ++ )
162 {
163 if ( relation[ i ][ i ] ) return -1;
164 }
165 return 0;
166 }
167
168 int top_sort( int n )
169 {
170 int cur;
171 int tot = 0;
172 bool select[ n ];
173 memset( select, false, sizeof( select ));
174 int indegree[ 27 ];
175 for ( int i = 0; i < n; i ++ )
176 {
177 indegree[ i ] = elem[ i ].in_degree;
178 }
179
180 while ( tot < n )
181 {
182 cur = -1;
183 for ( int i = 0; i < n; i ++ )
184 {
185 if ( indegree[ i ] == 0 && !select[ i ] )
186 {
187 if ( cur != -1 )
188 {
189 return has_circle( n );
190 }
191 cur = i;
192 }
193 }
194
195 if ( cur == -1 )
196 {
197 return -1; //
198 }
199 //printf( "--%d\n", cur );
200 sequence[ tot++ ] = cur;
201 select[ cur ] = true;
202 for ( int i = 0; i < elem[ cur ].out_degree; i ++ )
203 {
204 //elem[ elem[ cur ].out[ i ] ].in_degree --; // 最后发现这一句错了！！
205 indegree[ elem[ cur ].out[ i ] ] --;
206 }
207 }
208 return 1;
209 }
210
211 void solve( int n, int m )
212 {
213 char s[ 5 ];
214 int result;
215 bool not_determine = true;
216
217 if ( n == 1 )
218 {
219 sequence[ 0 ] = 0;
220 output( 0, n );
221 not_determine = false;
222 }
223
224 for ( int i = 1; i <= m; i ++ )
225 {
226 scanf( "%s", &s );
227 if ( not_determine )
228 {
229 add_relation_ship( s[0]-'A', s[2]-'A', n );
230 result = top_sort( n );
231 if ( result == 1 )
232 {
233 output( i, n );
234 not_determine = false;
235 }
236 else if ( result == -1 )
237 {
238 output( FIND_INCONSISTENCY, i );
239 not_determine = false;
240 }
241 }
242 }
243
244 if ( not_determine )
245 {
246 output( NOT_DETERMINE );
247 }
248 }
249
250 void initialize( int n )
251 {
252 memset( relation, 0, sizeof( relation ) );
253 for ( int i = 0; i < n; i ++ )
254 {
255 elem[ i ].in_degree = 0;
256 elem[ i ].out_degree = 0;
257 }
258 }
259
260 int main()
261 {
262 int n, m;
263 while ( true )
264 {
265 scanf( "%d %d", &n, &m );
266 if ( n == 0 && m == 0 ) break;
267 initialize( n );
268 solve( n,m );
269 // test( n );
270 }
271 return 0;
272 }
273