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 _________
Answer
60
Explanation
A DFS of an undirected graph grows one tree for each connected component: a new tree starts only when no unvisited vertex is reachable from the earlier ones. So the number of trees in the DFS forest equals the number of components.
A tree on \(t\) vertices has \(t - 1\) edges, so a forest with \(n\) vertices and \(c\) trees has \(n - c\) edges:
\[100 - c = 40 \quad\Rightarrow\quad c = 60\]
Edges of \(G\) that are not in the forest (back edges) do not change this, so \(G\) has 60 connected components.
Answer: 60