作者jb679123 (straw man)
看板Prob_Solve
标题[问题] DFS recursive algorithm
时间Tue Dec 30 01:02:29 2014
http://ppt.cc/wxbW
附图是用递回方式完成的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]
不知道这两个要怎麽用进去
--
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.123.103.109
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1419872555.A.43D.html
1F：推 fenzhang: DFS生成树没有cross edge。 12/30 02:44
2F：→ fenzhang: tree edge一定有某端是另一端父亲。 12/30 02:44
3F：→ scwg: 楼上在 undirected graph 里是对的, directed graph DPS 12/30 06:28
4F：→ scwg: 是可能有 cross edge 的. 原 po: 你的作法是什麽? 复杂度是? 12/30 06:29
5F：→ scwg: 用 color 判断有点奇怪, 因为 DFS 跑完每个点应该都是黑色.. 12/30 06:30
题目应该是问有向图，没有限定是DFS SPANNING TREE
我的想法是:
在u--->v的情况下 如果
u是gray v是white :tree edge
gray gray :back
gray black :若d[u]<d[v]则是forward 反之则是cross
※ 编辑: jb679123 (140.123.103.109), 12/30/2014 09:45:27
6F：→ scwg: 这个判断应该是对的, 可惜 u.color == gray 只有 DFS 到一半 12/30 13:40
7F：→ scwg: 的时候会成立. 想想看 u.d 和 u.f 存了什麽? 怎麽用他们重建 12/30 13:41
8F：→ scwg: 「u.color == gray」成立的「时间」? 12/30 13:41
恩恩 这也是目前卡住的地方ORZ
※ 编辑: jb679123 (140.123.103.109), 12/30/2014 15:15:53
9F：→ aaaaajack: 现在回好像有点迟XD 总之需要考虑各种edge的特性 01/05 23:01
10F：→ aaaaajack: forward跟back edge满足一个是另一个的ancestor 01/05 23:02
11F：→ aaaaajack: d跟f可以帮助你判断这件事 01/05 23:02
12F：→ aaaaajack: 然後pi帮助你判断他是不是tree edge 01/05 23:02
感谢a大的补充XDD
※ 编辑: jb679123 (140.123.214.127), 01/10/2015 16:03:42