之前 WA 好久= =。

給你一些大小關係,求是否有唯一的一個關係序列符合題目敘述,或判斷是否有無解情況。

假設 A>B,則建立一條邊 (A->B),可以得到以下訊息。

(1) 無解 -> 建圖中出現了 環。

(2) 有唯一解 -> 只有唯一的拓僕排序。

 

讓我們來回想一下 拓僕排序。

在一個 DAG 中,將G中所有點排成一序列。

使得G中任意頂點對<u, v>,若<u, v>是一條邊(u->v),則該序列中 u在v之前。

簡單分析:

(1) A->B->C->D    (2) A->B->C->A

(1) 最前面一定是 入度=0 的點。

(2) 若無 入度=0 的點,圖中有環。

 

算法 (1)

stack 實作。

a) 把 入度=0 的點 push。

b) 當 stack 非空

輸出 stack頂端元素v,pop。

檢查v 的出邊,把每條出邊所連到的頂點 入度-1,若該頂點 入度=0,push該頂點。

c) 當 stack 空

若輸出頂點數量<頂點數,表示有迴路,否則拓僕排序結束。

算法 (2)

DFS 實作。

從 root 開始 DFS,時間戳記,紀錄結束時間。

根據 時間戳記,由 大到小 排序。

 

有了以上這些知識,這題就不困難了。

我的code

http://codepad.org/oicEgBlw

p.s:  此題中,使用的是 算法(1)。

       c) 步驟中,輸出頂點數量<頂點數 有兩種結果,一種是有環,或是還沒有答案。

       所以我先用 Floyed 判斷是否有環,這樣假若 輸出頂點數量<頂點數,就只有 沒有答案 一種結果了。

 

 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()