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