GATE 2024 CS (CS1) – Question 60
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
- GATE 2024 CS (CS2) Q59
- GATE 2023 CS Q56
- GATE 2022 CS Q49
- GATE 2021 CS (CS1) Q27
- GATE 2021 CS (CS1) Q46
- GATE 2021 CS (CS1) Q51
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →