Topological Sort & SCC MCQs: 12 Solved GATE Questions with Explanations

Topological-sort options often differ by one misplaced prerequisite. SCC and DFS questions shift the task from ordering to mutual reachability, tree edges, or timestamp intervals. Convert each option into edge constraints, two-way paths, or nested DFS intervals before choosing.

GATE questions combine topological ordering, mutual reachability, and DFS traversal. Choose an option, or write the NAT value, before reading each explanation. KnowledgeGate has over 20 practice questions on Topological Sort and SCC. Prerequisite constraints lead into reachability and traversal reasoning throughout the GATE CS Exam Preparation syllabus.

Topological sort and SCC rules to fix before the questions

For {A,B,C,D,E} with A->C, B->C, C->D, C->E, indegrees start as A:0, B:0, C:2, D:1, E:1. A then B releases C; D/E and the initial A/B may swap. The four orders are A B C D E, A B C E D, B A C D E, B A C E D.

For 1->2, 2->3, 3->1, 3->4, 4->5, 5->4, mutual reachability gives SCCs {1,2,3} and {4,5}. Contraction leaves {1,2,3}->{4,5}, a two-vertex DAG. Graph Algorithms: BFS, DFS, and Shortest Paths Worked Out owns traversal mechanics and shortest-path reasoning. Here DFS matters where its forest, finish times, and transpose reasoning support SCC decomposition and the condensation DAG.

Topological sort MCQs 1-3: prerequisites and counting orders

GATE 2024 Question 1

Consider the directed acyclic graph (DAG) below:

Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?

• A. P Q R S T U V

• B. P R Q V S U T

• C. P Q R S V U T

• D. P R Q S V T U

Answer: B and D. Constraints are P<Q, R<Q, Q<S, Q<V, S<U, V<T; A/C violate R<Q, while B/D satisfy all six.

GATE 2016 Question 2

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is ______________ .

Answer: 6. With a first and f last, interleaving b<c and d<e gives C(4,2)=6: bcde, bdce, bdec, dbce, dbec, debc.

GATE 2014 Question 3

Consider the directed graph below given.

Which one of the following is TRUE?

• A. The graph does not have any topological ordering.

• B. Both PQRS and SRQP are topological orderings.

• C. Both PSRQ and SPRQ are topological orderings.

• D. PSRQ is the only topological ordering.

Answer: C. From P->Q, P->R, S->Q, S->R and R->Q, only P and S may swap, giving exactly P S R Q and S P R Q.

Topological sort MCQs 4-5: reject one order and trace search order

GATE 2007 Question 4

Consider the DAG with V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?

• A. 1 2 3 4 5 6

• B. 1 3 2 4 5 6

• C. 1 3 2 4 6 5

• D. 3 2 4 1 6 5

Answer: D. A, B and C respect 1->2, 1->3, 2->4, 2->5, 3->4, 3->6, 4->5, 4->6, but D puts 2 and 3 before 1.

GATE 2024 Question 5

Consider a state space where the start state is number 1. The successor function for the state numbered n returns two states numbered n+1 and n+2. Assume that the states in the unexpanded state list are expanded in the ascending order of numbers and the previously expanded states are not added to the unexpanded state list.

Which ONE of the following statements about breadth-first search (BFS) and depth-first search (DFS) is true, when reaching the goal state number 6?

• A. BFS expands more states than DFS.

• B. DFS expands more states than BFS.

• C. Both BFS and DFS expand equal number of states.

• D. Both BFS and DFS do not reach the goal state number 6.

Answer: C. The ascending pending-state rule overrides queue or stack intuition, making both traces 1,2,3,4,5,6, so each search expands six states.

Strongly connected component MCQs 6-7: transpose and decomposition

GATE 2014 Question 6

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. $G_1 = (V,E_1)$ where $E_1 = \left\{(u,v) \mid (u,v) \notin E\right\}$

• B. $G_2 = (V,E_2)$ where $E_2 = \left\{(u,v) \mid (v,u) \in E \right\}$

• C. $G_3 (V,E_3)$ where $E_3 = \{(u,v) \mid$ there is a path of length $\leq2$ from $u$ to $v$ in $E\}$

• D. $G_4 = (V_4,E)$ where $V_4$ is the set of vertices in $G$ which are not isolated

Answer analysis: B is the expected choice, but B and C are mathematically valid as written. Reversing every edge preserves mutual reachability, so B keeps the SCC partition. Option C includes every original edge as a length-one path and adds only shortcuts for paths that already exist. It therefore preserves reachability and the SCC partition too. The wording makes the item ambiguous.

GATE 2006 Question 7

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

• A. {P, Q, R, S}, {T}, {U}, {V}

• B. {P,Q, R, S, T, V}, {U}

• C. {P, Q, S, T, V}, {R}, {U}

• D. {P, Q, R, S, T, U, V}

Answer: B. P, Q, R, S, T and V are mutually reachable; U is not and stays singleton {U}.

DFS MCQs 8-10: edge classes, forest size and timestamps

GATE 2024 Question 8

Let 𝐺 be a directed graph and 𝑇 a depth first search (DFS) spanning tree in 𝐺 that is rooted at a vertex 𝑣. Suppose 𝑇 is also a breadth first search (BFS) tree in 𝐺, rooted at 𝑣. Which of the following statements is/are TRUE for every such graph 𝐺 and tree 𝑇 ?

• A. There are no back-edges in 𝐺 with respect to the tree 𝑇

• B. There are no cross-edges in 𝐺 with respect to the tree 𝑇

• C. There are no forward-edges in 𝐺 with respect to the tree 𝑇

• D. The only edges in 𝐺 are the edges in 𝑇

Answer: C. A non-tree forward edge to a deeper descendant would shorten its BFS path, while back and cross edges can still exist. At depth d+1, the ancestor edge is the tree edge.

GATE 2005 Question 9

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

• A. k

• B. k + 1

• C. n - k - 1

• D. n - k

Answer: D. Since k=sum(v_i-1)=n-c, c=n-k; for n=7, k=4, three components can have 3, 2 and 2 vertices.

GATE 2006 Question 10

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that

d(P) = 5 units     f(P) = 12 units

d(Q) = 6 units     f(Q) = 10 units

d(R) = 14 unit     f(R) = 18 units

which one of the following statements is TRUE about the graph

• A. There is only one connected component

• B. There are two connected components, and P and R are connected

• C. There are two connected components, and Q and R are connected

• D. There are two connected components, and P and Q are connected

Answer: D. With P=[5,12], Q=[6,10], R=[14,18], Q nests inside P's DFS tree while R starts another, giving {P,Q} and {R}.

Connectivity MCQs 11-12: traversal cost and adjacent swaps

GATE 2008 Question 11

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

• A. θ(n)

• B. θ(m)

• C. θ(m + n)

• D. θ(mn)

Answer: C. Adjacency lists process n vertices and two entries per edge, so Theta(n+2m)=Theta(n+m); neither term alone suffices.

GATE 2018 Question 12

Let $G$ be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, … , 100. There is an edge between vertices 𝑢 and 𝑣 if and only if the label of 𝑢 can be obtained by swapping two adjacent numbers in the label of 𝑣. Let 𝑦 denote the degree of a vertex in $G$, and 𝑧 denote the number of connected components in $G$. Then, 𝑦 + 10𝑧 = _____.

Answer: 109. The 99 adjacent pairs give y=99; adjacent swaps connect all permutations, so z=1 and 99+10(1)=109.

Topological sort and SCC traps: next practice

45-second routine: write constraints, reject violations, fix endpoints, count. Test SCCs two-way. For DFS, draw intervals; use tree edges = vertices - components.

The earlier Graph MCQs: 10 Solved Questions on Representations, BFS, DFS and Connectivity set owns representations, traversal, and broad connectivity. Its transpose, DFS-forest, and traversal-cost questions reappear here because those invariants underpin SCC preservation and condensation-graph algorithms. Coding for Placements covers implementation; GATE Guidance by Sanchit Sir gives the GATE CS sequence.

Short version: topological sort orders DAG vertices under edge constraints, SCCs group mutually reachable vertices, and DFS bridges them.