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