[問題] DFS recursive algorithm

[jb679123 (straw man)]

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://www.ptt.cc/bbs/Prob_Solve/M.1419872555.A.43D.html
推 fenzhang: DFS生成樹沒有cross edge。
→ fenzhang: tree edge一定有某端是另一端父親。
→ scwg: 樓上在 undirected graph 裡是對的, directed graph DPS
→ scwg: 是可能有 cross edge 的. 原 po: 你的作法是什麼? 複雜度是?
→ scwg: 用 color 判斷有點奇怪, 因為 DFS 跑完每個點應該都是黑色..
題目應該是問有向圖，沒有限定是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
→ scwg: 這個判斷應該是對的, 可惜 u.color == gray 只有 DFS 到一半
→ scwg: 的時候會成立. 想想看 u.d 和 u.f 存了什麼? 怎麼用他們重建
→ scwg: 「u.color == gray」成立的「時間」?
恩恩  這也是目前卡住的地方ORZ
※ 編輯: jb679123 (140.123.103.109), 12/30/2014 15:15:53
→ aaaaajack: 現在回好像有點遲XD 總之需要考慮各種edge的特性
→ aaaaajack: forward跟back edge滿足一個是另一個的ancestor
→ aaaaajack: d跟f可以幫助你判斷這件事
→ aaaaajack: 然後pi幫助你判斷他是不是tree edge
感謝a大的補充XDD
※ 編輯: jb679123 (140.123.214.127), 01/10/2015 16:03:42