作者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