POJ 1094 Sorting It All Out

題意：
    給定N表示有N個點，M表示底下有M行關係式，然後一行一行讀取關係式：

• 如果在第i行發現已經能明確將所有點排出順序(也就是只有一種答案)，輸出Sorted sequence determined after i relations: ...(順序)
• 如果在第i行發現和之前的關係式有衝突(形成一個環，例如A>B>C>A)，則輸出Inconsistency found after i relations.
• 如果讀取到最後關係都沒有衝突但也找不到唯一答案，則輸出Sorted sequence cannot be determined.

想法：

    每次讀取關係式的時候就檢查是否有衝突(形成一個環)，如果沒有再去找topological sort，topological sort這function裡面要判斷是否為唯一解，因此只能選一條路徑往下遞迴，最後判斷答案優先順序為1.先看有沒有衝突2.看有沒有解，再依題目敘述輸出即可，詳細看底下code。

POJ 2367 Genealogical tree

題意：
    第一行N表示有N個數(編號1~N)，接下來N行每行有幾個數字，第i行表示數字i需要在第i行那些數前面，例如Sample Input的4 5 1 0表示數字2需要在4,5,1的前面，以數字0代表該行的終止。

想法：
    建立graph，從起點(沒有其他點連入)開始用DFS走遍整個graph，並記下走過的順序，最後再逆向輸出就是一個topological sort。

UVa 872 Ordering

想法：
    這題是backtracking內融合了topological sort，基本上就是第一格, 第二格, ....依序填入，每次填的時後判斷哪些node可以填(表示需要在該node前出現的node已經出現過了)，詳細見底下code。

UVa 10305 Ordering Tasks

想法：
    輸出只要符合是一個topological sort即可，因此可以從起點(沒有被任何點連入的點)用DFS走遍，並同時記錄走遍的點，最後再逆向輸出這些點就是一個topological sort。

UVa 11606 Pick up sticks

想法：

    把放在最上面(也就是這個點沒有其他點連入)的stick當做起點，用DFS走遍，並將走遍的經過的點記錄下來，最後逆向輸出這些記錄的點就是一個topological sort。

UVa 200 Rare Order

題意：
　　Input給的那些字串是每個index的名稱，而這些Index是照"某個字典序"由小到大排好的(就像一般的目錄是從A~Z排好)，我們要從Input裡面判斷這些字的字典序。例如Sample Input：
  XWY
  ZX
  ZXY
  ZXW
  YWWX
    我們可以從XWY和ZX判斷X<Z，ZXY和ZXW判斷Y<W，ZXW和YWWX判斷Z<Y，所以可以得到X<Z<Y<W。

**本題測資只有一個**

想法：
　　一次兩行判斷，找出誰<誰，記錄完之後，從沒有被連入的點當做起點，使用DFS走遍並記下走遍的點，將記下的點逆向輸出就是一個topological sort。

UVa 11060 Becerages

想法：
　　記錄每個點被其他點連入的數量(Ex: A->B, C->B，則beConnected[B]=2)，和記錄各個點連到哪些點。

1. 每次從頭找beConnected[i]==0(表示沒有點連到i)的Node
2. 將這個Node輸出
3. 同時將beConnected[i]改成-1表示這Node已經輸出過了
4. 然後其他每個被Node i連入的Node j，把beConnected[j]--
5. 執行1~4 N次，把每個Node都輸出過