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 ? A) G1 = (V, E1) where E1 = $u, v) (u, v) E\ B) G2 = (V, E2) where E2 = \(u, v) (v, u) E\ C) G3 = (V, E3) where E3 = \(u, v) there is a path of length 2 from u to v in E\ D) G4 = (V4, E) where V4 is the set of vertices in G which are not isolated$

Official answer: B) G2 = (V, E2) where E2 = \(u, v) (v, u) E\. Explanation: Two vertices u and v belong to the same strongly connected component (SCC) in G if and only if there is a directed path from u to v and a directed path from v to u in G. In the transpose graph GT = G2 = (V, E2), where E2 = \(u, v) (v, u) E\, every edge direction is reversed. - If there is a path from u to v in G, there is a path from v to u in GT. - If there is a path from v to u in G, there is a path from u to v in GT. Therefore, vertices u and v are mutually reachable in G if and only if they are mutually reachable in GT. Hence, the transpose graph G2 has exactly the same strongly connected components as G, making (B) the correct option.

A) G1 = (V, E1) where E1 = \(u, v) (u, v) E\

B) G2 = (V, E2) where E2 = \(u, v) (v, u) E\

C) G3 = (V, E3) where E3 = \(u, v) there is a path of length 2 from u to v in E\

D) G4 = (V4, E) where V4 is the set of vertices in G which are not isolated\)

Algorithms · Graph Traversals

Official IIT answer key · IIT Kharagpur · Audited Aug 2026

Take topic test

GATE CSE 2014 Set 1 Q3 · MCQ · 1 mark

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$ ?

Select an option to check

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals

GATE tests Graph Traversals (BFS and DFS) through deep theoretical properties rather than simple code tracing. Key emphases include edge classification (tree, back, forward, cross edges), timestamp intervals via the Parenthesis Theorem, DAG topological orderings, and structural invariants like the BFS level difference inequality and tree height versus graph diameter. Recent papers heavily favor MSQs and multi-property conceptual deductions over simple single-answer lookups.

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Algorithms · Graph Traversals

Official IIT answer key · IIT Kharagpur · Audited Aug 2026

Take topic test

GATE CSE 2014 Set 1 Q3 · MCQ · 1 mark

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$ ?

Select an option to check

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

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$ ?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2014 Set 1

More on Graph Traversals

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$ ?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2014 Set 1

More on Graph Traversals

Let G=(V,E)G=(V,E)G=(V,E) be a directed graph where VVV is the set of vertices and EEE the set of edges. Then which one of the following graphs has the same strongly connected components as GGG ?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2014 Set 1

More on Graph Traversals

Share this solution

Let G=(V,E)G=(V,E)G=(V,E) be a directed graph where VVV is the set of vertices and EEE the set of edges. Then which one of the following graphs has the same strongly connected components as GGG ?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2014 Set 1

More on Graph Traversals

Share this solution

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$ ?

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$ ?