網頁

2014年3月7日 星期五

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。


2 則留言: