網頁

2014年3月10日 星期一

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。