The GATE Grind

GATE 2024 CS (CS1) – Question 60

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

The number of edges present in the forest generated by the DFS traversal of an undirected graph $G$ with 100 vertices is 40. The number of connected components in $G$ is _________

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 60

Explanation

**1. Describe a DFS forest.** DFS creates one rooted tree for each connected component, including a single-vertex tree for an isolated vertex. A tree with nᵢ vertices has nᵢ−1 edges.

**2. Sum over the components.** With c components and 100 vertices, total forest edges are $\sum(n_i-1)=\sum n_i-c=100-c$. These are DFS-tree edges, not every edge of the original graph.

**3. Solve the count equation.** $100-c=40$ gives **c = 60 connected components**. The relation remains valid even when the original graph contains cycles.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →