IAE Academy

GATE 2026 CS1 Q.50: solution and answer

GATE 2026 · CS1Q.50 · 2 marks · MSQ

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph as input, where and are the discovery time and finishing time, respectively, of the vertex .

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 is a directed acyclic graph (DAG).

For an edge , which of the following options will NEVER be correct?

GATE 2026 CS1 question 50: Two side-by-side pseudocode blocks (not a diagram): the left block, DFS(G), unmarks all vertices, initializes t=0, and…Tap to open full size
Figure from the GATE 2026 CS1 paper. It is part of the question.
Figure description

Two side-by-side pseudocode blocks (not a diagram): the left block, DFS(G), unmarks all vertices, initializes t=0, and for each unmarked vertex calls Explore, updating t with the return value. The right block, Explore(G, v, t), marks v, increments t, sets d[v]=t, iterates over all out-edges (v,w) of v, recursively calling Explore(G,w,t) if w is unmarked (updating t), then after the loop increments t, sets f[v]=t, and returns t.

  1. (A)

  2. (B)

  3. (C)

  4. (D)

Answer and solution

ANSWER

The correct answer is B and D — options B (the back-edge interval pattern, impossible in a DAG since DAGs have no back edges) and D (a partially overlapping interval pattern, impossible in any DFS by the parenthesis theorem) will never be correct for an edge (u,v).

Official answer: B, DSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

  1. Recall the DFS Parenthesis Theorem: for any edge (u,v) processed during DFS, the discovery/finish intervals [d[u],f[u]] and [d[v],f[v]] must be either completely nested or completely disjoint — never partially overlapping — regardless of whether the graph is cyclic or acyclic.

  2. Option (A): d[u]<d[v]<f[v]<f[u] is the tree/forward-edge pattern (v's interval nested inside u's, u discovers v). This is a valid, common occurrence, including in a DAG. So (A) CAN be correct.

  3. Option (C): d[v]<f[v]<d[u]<f[u] is the cross-edge pattern (v's interval entirely finished before u's interval starts, e.g. edge into an already-explored earlier subtree). This is allowed in a DAG since it creates no cycle. So (C) CAN be correct.

  4. Option (B): d[v]<d[u]<f[u]<f[v] is the back-edge pattern (u's interval nested inside v's, meaning v is an ancestor of u still open on the DFS stack when edge (u,v) is traversed). A back edge always implies a cycle, formed by the tree-edge path from v down to u plus the back edge (u,v) closing it. Since G is a DAG, it has no cycles, so it has no back edges. Hence pattern (B) NEVER occurs.

  5. Option (D): d[u]<d[v]<f[u]<f[v] describes intervals that partially overlap — neither nested nor disjoint. By the parenthesis theorem, this configuration is structurally impossible for ANY DFS on ANY directed graph (the recursive call/return discipline forces nesting or disjointness), independent of the DAG condition. Hence pattern (D) also NEVER occurs.

  6. Therefore the two interval patterns that will never be correct for an edge (u,v) are (B) and (D).

KEY IDEA

The DFS Parenthesis Theorem gives exactly four possible relations between the [d,f] intervals of two vertices u, v for an edge (u,v): tree/forward (nested, u outer), back (nested, v outer), cross (disjoint, v's interval entirely before u's), and a fourth "partial overlap" pattern, which the theorem rules out for ANY DFS on ANY directed graph — it is not graph-type dependent. Separately, a DAG has no back edges by definition (a back edge always creates a cycle with the tree-path from v to u). So one excluded pattern (D) comes from the parenthesis theorem itself, and the other (B) comes specifically from the DAG constraint — the two impossibilities have different sources, but both must be excluded here.

WATCH OUT FOR

Two distinct traps: (1) treating this as "there is only one impossible pattern" — students often stop after correctly ruling out the back-edge pattern via the DAG property and forget that option D is ALSO impossible, but for the separate, more fundamental reason (parenthesis theorem) that has nothing to do with the graph being acyclic. (2) Confusing which nesting direction is the back edge: back edge is v (ancestor, still open) containing u (descendant) — i.e., d[v] < d[u] < f[u] < f[v] — not the other nesting direction, which is the tree/forward-edge pattern.

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

More Graph algorithms questions