A depth-first search is performed on a directed acyclic graph. Let d[u] denote…
GATE · 2007 · IT
A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph ?
- A.
d[u] < d[v]
- B.
d[u] < f[v]
- C.
f[u] < f[v]
- D.
f[u] > f[v]
Attempted by 308 students.
Show answer
Correct answer: D
Explore the full course: Iocl Engineers Officers Grade A Paper 2
Loading lesson…