作者sbshank (季)
看板Prob_Solve
標題[問題] 有向圖的自達點
時間Wed Nov 16 22:02:58 2011
給定一個有向圖
要找所有能從自己經過某個path回到自己的node
除了一一測試Reachability以外
有什麼好的演算法可以用
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.24.243
1F：推 suhorng:找出SCC. 所有在點數>1的SCC中的點必定可以,反之不行 11/16 23:08
2F：→ suhorng:其時間複雜度為O(V+E) 11/16 23:08
3F：推 ckclark:有loop的話一個點也可以 11/17 00:32
4F：→ suhorng:樓上有道理....self-cycle要Special Case判掉orz 11/17 08:16
5F：→ firejox:用floyd-warshall (V^3)偷懶解決XD 11/17 19:49