作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [DS]-中央95资结
时间Wed Feb 10 09:41:08 2010
※ 引述《NOtWorThy (分子小於64)》之铭言：
: 如题 中央资结95考古题 第7题
: 不知是否理解错误
: 或有其他想法
: 烦请高手赐教
: 谢谢!!
Floyd Algorithm计算到第k回合的时候，是判断出顶点i~顶点j存不存在有只
使用顶点编号 < k的路径，所以应该没办法拿来判断回圈？
所以可以用另外一种求Transitive Closure的方法，就是Adjacency Matrix相乘法。
（不是数学的乘法..）
乘一次代表顶点i到顶点j有没有长度为2的路径，所以乘三次之後就知道
有没有长度为4的路径了。时间复杂度就是跟矩阵乘法一样，看你要用哪种演算法。
不过还有另外一种想法，如果a, b, c, d四个点形成回圈，那麽a必定连向b, d，
且c也连向b, d，只要穷举所有a, c对，看看他们有没有共同相连的两点就可以。
a, c对有O(n^2)个，而判断共同相连的点只需要O(n)，复杂度为O(n^3)。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：→ taitin:恩，我推文说错了 02/10 10:48