GATE 2026 · CS1 - Forenoon
Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph G(V,E) as input, where d[v] and f[v] are the discovery time and finishing time, respectively, of the vertex v in V.
DFS(G):
unmark all v in V
t <- 0
for each v in V
if v is unmarked
t <- Explore(G, v, t)
end if
end for
Explore(G, v, t):
mark v
t <- t + 1
d[v] <- t
for each (v, w) in E
if w is unmarked
t <- Explore(G, w, t)
end if
end for
t <- t + 1
f[v] <- t
return t
Suppose that the input directed graph G(V,E) is a directed acyclic graph (DAG).
For an edge (u,v) in E, which of the following options will NEVER be correct?