[问题] DFS recursive algorithm
楼主: jb679123 (straw man) 2014-12-30 01:02:29
附图是用递回方式完成的DFS算法
如果我们要根据算法回传的
d[u],f[u],pi[u],d[v],f[v],pi[v]
去判断(u,v)是否为tree back forward 或cross edge
且要在O(1)的时间内
请问一下该怎么判断?
目前只想到是用color和d(u) d(v)去判断
但题目要求要f[x]还有pi[x]
不知道这两个要怎么用进去
作者: fenzhang (分帐) 2014-12-30 02:44:00
DFS生成树没有cross edge。tree edge一定有某端是另一端父亲。
作者: scwg ( ) 2014-12-30 06:28:00
楼上在 undirected graph 里是对的, directed graph DPS是可能有 cross edge 的. 原 po: 你的作法是什么? 复杂度是?用 color 判断有点奇怪, 因为 DFS 跑完每个点应该都是黑色..这个判断应该是对的, 可惜 u.color == gray 只有 DFS 到一半的时候会成立. 想想看 u.d 和 u.f 存了什么? 怎么用他们重建“u.color == gray”成立的“时间”?
作者: aaaaajack (丁丁是个人才) 2013-01-05 23:01:00
现在回好像有点迟XD 总之需要考虑各种edge的特性forward跟back edge满足一个是另一个的ancestord跟f可以帮助你判断这件事然后pi帮助你判断他是不是tree edge
继续阅读
[问题] johnson algorithmjb679123[问题] 类似背包问题cutekidRe: [问题] 记忆游戏 (更新暴力法解随机翻的情况, 求正常翻的机率)LPH66Re: [问题] 记忆游戏 (更新暴力法解随机翻的情况, 求正常翻的机率)flereRe: [问题] 记忆游戏 (更新暴力法解随机翻的情况, 求正常翻的机率)LPH66[问题] 记忆游戏 (更新暴力法解随机翻的情况, 求正常翻的机率)GenialPP[问题] 以已知数反推其位于数列中第几项unsh[问题] 一串数字中找到相同的两个数penknifelee[问题] beam searchcsam11000[讨论] perfect hashingsandy4444