GateAI
Graph Traversals

GATE CSE 2014 Set 1 · Q3

MCQ1 markEasy

Time

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

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) G2 = (V, E2) where E2 = {(u, v) (v, u) ∈ E}

Graph Traversals

Two vertices uu and vv belong to the same strongly connected component (SCC) in GG if and only if there is a directed path from uu to vv and a directed path from vv to uu in GG.

In the transpose graph GT=G2=(V,E2)G^T = G_2 = (V, E_2), where E2={(u,v)∣(v,u)∈E}E_2 = \{(u, v) \mid (v, u) \in E\}, every edge direction is reversed.

  • If there is a path from uu to vv in GG, there is a path from vv to uu in GTG^T.

  • If there is a path from vv to uu in GG, there is a path from uu to vv in GTG^T.

Therefore, vertices uu and vv are mutually reachable in GG if and only if they are mutually reachable in GTG^T. Hence, the transpose graph G2G_2 has exactly the same strongly connected components as GG, making (B) the correct option.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

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

Where do you stand for GATE?

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.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Graph Traversals in GATE CSE

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 Traversals

More from GATE CSE 2014 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2014 Set 1 · Q3 · MCQ

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

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