The GATE Grind

GATE 2014 CS (CS1) – Question 13

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple choice

Let G = (V,E) be a directed graph. Which graph has the same strongly connected components as G?

  1. $G_1=(V,E_1)$, $E_1=\{(u,v):(u,v)\notin E\}$
  2. $G_2=(V,E_2)$, $E_2=\{(u,v):(v,u)\in E\}$
  3. $G_3=(V,E_3)$, where $(u,v)\in E_3$ iff there is a path of length at most 2 from u to v in E.
  4. $G_4=(V_4,E)$, where $V_4$ contains the nonisolated vertices of G.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $G_2=(V,E_2)$, $E_2=\{(u,v):(v,u)\in E\}$

Explanation

Reversing every edge reverses paths, preserving mutual reachability and hence strongly connected components. Thus B is the official answer. As printed, C also preserves components: every original edge is included as a length-one path, and every added length-two edge merely shortcuts an existing path, so reachability is unchanged. D removes isolated singleton components; A need not preserve reachability. The single-choice premise is therefore ambiguous between B and C.