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]
不知道這兩個要怎麼用進去

DFS生成樹沒有cross edge。tree edge一定有某端是另一端父親。

樓上在 undirected graph 裡是對的, directed graph DPS是可能有 cross edge 的. 原 po: 你的作法是什麼? 複雜度是?用 color 判斷有點奇怪, 因為 DFS 跑完每個點應該都是黑色..這個判斷應該是對的, 可惜 u.color == gray 只有 DFS 到一半的時候會成立. 想想看 u.d 和 u.f 存了什麼? 怎麼用他們重建「u.color == gray」成立的「時間」?

現在回好像有點遲XD 總之需要考慮各種edge的特性forward跟back edge滿足一個是另一個的ancestord跟f可以幫助你判斷這件事然後pi幫助你判斷他是不是tree edge