The number of edges present in the forest generated by the DFS traversal of an…
2024
The number of edges present in the forest generated by the DFS traversal of an undirected graph 𝐺 with 100 vertices is 40. The number of connected components in 𝐺 is _________
Attempted by 102 students.
Show answer & explanation
Correct answer: 60
Key idea: In the DFS forest of an undirected graph, each connected component with k vertices contributes k−1 edges.
Let c be the number of connected components. The total number of vertices is 100, so the DFS forest has 100 − c edges.
Given the DFS forest has 40 edges, set 40 = 100 − c. Solving gives c = 100 − 40 = 60.
Answer: 60 connected components.
A video solution is available for this question — log in and enroll to watch it.