→ yyc1217:我的想法是紀錄每個點的顏色 首先全部都是白色 02/27 23:48
→ yyc1217:起點是黑色 接下來把起點連到的所有點都標為黑色 02/27 23:48
→ yyc1217:並且把所有點連回起點的路徑刪掉 02/27 23:49
→ yyc1217:最後若遇到下一個點是黑色的 則表示有cycle 02/27 23:49
→ yyc1217:不知道這樣對不對= = 02/27 23:50
→ polomoss:利用back edge,其他大同小異 02/28 00:02
推 uminchu185:用一般的DFS就可以了, 發現back edge立刻終止程式 02/28 08:17
推 FRAXIS:應該是無向圖吧 -> acyclic圖的邊數 < |V| -> DFS修改一下. 02/28 08:19
→ uminchu185:|E|的檢查個數不會超過|V|, cost=O(|V|+|V|)=O(V) 02/28 08:20
→ hungyanbin:好像是耶......那時候想太多了 慘~~~~~ 02/28 11:12