Skip to content
GATEiit

GATE CSE 2026 Session 1 Q50: Impossible DFS discovery/finish orderings for a DAG edge

Question

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph G(V,E)G(V, E) as input, where d[v]d[v] and f[v]f[v] are the discovery time and finishing time, respectively, of the vertex v∈Vv \in V.

DFS(G):
   unmark all v ∈ V
   t ← 0
   for each v ∈ 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) ∈ 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)G(V, E) is a directed acyclic graph (DAG).

For an edge (u,v)∈E(u, v) \in E, which of the following options will NEVER be correct?

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: B, D (official GATE 2026 final answer key)

Concept used: Parenthesis theorem plus edge classification: a DAG has no back edges, so f[v]<f[u]f[v] < f[u] for every edge (u,v)(u, v).

First step: Option B nests uu inside vv, which makes (u,v)(u, v) a back edge; option D interleaves intervals, which DFS never produces.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 1 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2026 Session 1 questions →