[問題] 有向圖的自達點

看板Prob_Solve作者 (季)時間14年前 (2011/11/16 22:03), 編輯推噓2(2推 0噓 3→)
留言5則, 3人參與, 最新討論串1/1
給定一個有向圖 要找所有能從自己經過某個path回到自己的node 除了一一測試Reachability以外 有什麼好的演算法可以用 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.24.243
推
11/16 23:08, , 1F
找出SCC. 所有在點數>1的SCC中的點必定可以,反之不行
11/16 23:08, 1F
→
11/16 23:08, , 2F
其時間複雜度為O(V+E)
11/16 23:08, 2F
推
11/17 00:32, , 3F
有loop的話一個點也可以
11/17 00:32, 3F
→
11/17 08:16, , 4F
樓上有道理....self-cycle要Special Case判掉orz
11/17 08:16, 4F
→
11/17 19:49, , 5F
用floyd-warshall (V^3)偷懶解決XD
11/17 19:49, 5F
‣ 更多 sbshank 的文章
文章代碼(AID): #1EmyAL87 (Prob_Solve)