GATE CS 2024 Set 1 — Question 60

In an undirected graph with $n$ vertices and $k$ connected components, any spanning forest (including one generated by DFS) will have exactly $n - k$ edges.Given:

• Number of vertices ($n$) = 100
• Number of edges in the DFS forest = 40

Calculation:
Using the formula for the number of edges in a forest:$$\text{Number of edges} = n - k$$$$40 = 100 - k$$$$k = 100 - 40 = 60$$Therefore, the number of connected components in $G$ is 60.