好久沒寫程序練手了，今天本來準(zhǔn)備拿POJ1025開刀的，但是1025這個模擬題目太
繁雜了，換一個，寫POJ1094，結(jié)果郁悶地寫了三個多小時——代碼水平有待提升呀。
     下面是我寫這個題目的詳細(xì)過程，跟大家分享下：

題目地址：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1094

題目描述：
       一個升序串是一群用小于號連接起來的由小到大排列好的數(shù)值。例如，一個排好的序列 A, B, C, D 就表示 A < B, B < C 還有 C < D。現(xiàn)在，給你一堆格式為 A < B 的關(guān)系式給你，然后你就要去判斷有沒有一個可以排列的順序。
Input
       輸入數(shù)據(jù)由多組測試數(shù)據(jù)組成。每一組測試數(shù)據(jù)的第一行是兩個整數(shù)n 和 m。 第一個整數(shù)代表有多少個字母要排列，而且 2 <= n <= 26。要排列的字母是大寫字母中的前n個。 第二個整數(shù)m表示會出現(xiàn)多少組像 A < B 這樣的數(shù)值關(guān)系。下面的m行，每一行有一個只有三個字符的關(guān)系式：一個大寫字母，符號“<”和另一個大寫字母。除了前n個大寫字母以外，不會其他字母字母。當(dāng) n = m = 0 時表示輸入結(jié)束。
Output
       對應(yīng)每組輸入數(shù)據(jù)，輸出只有一行。這一行要是以下三種情況之一：
Sorted sequence determined after xxx relations: yyy…y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
xxx 就是當(dāng)一個升序序列確定時或者發(fā)現(xiàn)有矛盾時所處理到的第幾個關(guān)系式，哪種情況先出現(xiàn)，就輸出哪種；而 yyy…y 就是排好序的升序序列。

××××××××××××××××××××××××××××××××××××××××××××××××××××××

下面是正題：
 
        我拿到題目就認(rèn)為這個題目的算法很簡單——不就拓?fù)渑判蚵铩５幸稽c比較關(guān)鍵：需要每輸入一個關(guān)系就判斷一次。不過總共的元素最多才26個，時間應(yīng)該是夠用的。

      然后就寫，很快寫完，過了樣例，檢查了一下，提交，WA,
      兩個錯誤原因，一個是一條語句（見下面注釋）。
     一個是沒有判斷環(huán)。

     然后我就用DFS判斷環(huán)。
     第二次得到TLE。

 

    后面想了下DFS太慢，改進(jìn)用矩陣判斷是否有回路。
    第三次得到WA。.

    然后重寫，還是WA。怎么回事？

    然后看Discuss吧。
    發(fā)現(xiàn)一組數(shù)據(jù)過不了
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.

   原來太急躁了，樣例都沒過——我把矩陣與元素之間得關(guān)系弄一起了，郁悶了。
   然后再改吧。

    這回沒有過，我還是發(fā)現(xiàn)了錯誤，
    1 0
    這一組都過不了。

    改了再交，就是WA!!!???
    終于找到了一句，每次排序后把元素的入度改了，
   
    改好后交，還是WA.
    原來沒有刪掉測試數(shù)據(jù)，太急躁了，BS下自己，這種錯誤不能有。

   刪掉測試數(shù)據(jù)，終于AC了。
 

總結(jié)：

       最后算法跟開始想的方向一樣，主要是具體實現(xiàn)有問題——而且都是細(xì)節(jié)，主要反映在對數(shù)據(jù)挖掘得不夠上。

        自己很久沒寫代碼解題了，更加久沒寫圖論的題目了，現(xiàn)在考試只剩下專業(yè)課了，我可以適當(dāng)放手開始寫代碼了——手生得厲害，我畢竟跟那些過分注重成績的人不是一樣的，還是做自己喜歡的事吧。
        
下面是代碼（很亂，加了我寫代碼的一系列過程中的調(diào)試注釋）：