Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2014 Set 1 · Q3
Time
Select one answerSingle correct
Solution
Official answer: B) G2 = (V, E2) where E2 = {(u, v) (v, u) ∈ E}
Graph TraversalsTwo vertices and belong to the same strongly connected component (SCC) in if and only if there is a directed path from to and a directed path from to in .
In the transpose graph , where , every edge direction is reversed.
If there is a path from to in , there is a path from to in .
If there is a path from to in , there is a path from to in .
Therefore, vertices and are mutually reachable in if and only if they are mutually reachable in . Hence, the transpose graph has exactly the same strongly connected components as , making (B) the correct option.
Try the question first, then check your work.
Examiner trap
Reversing all edges in a directed graph (transpose graph) preserves mutual reachability between every pair of vertices.
This Graph Traversals previous year question is Q3 of the GATE CSE 2014 Set 1 paper. Find more GATE CSE PYQs on Graph Traversals in Algorithms, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Graph Traversals PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Graph Traversals has 16 GATE CSE PYQs across 12 papers from 2014 to 2026. 5 of them are 1-mark MCQs like this one, and GATE CSE 2014 Set 1 has 3.
How GATE tests Graph TraversalsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.