GATE CS 2024 Set 1 Q50 — Graph Traversals (BFS, DFS)

A Depth-First Search ($\text{DFS}$) traversal of an undirected graph $G = (V, E)$ produces a spanning forest (DFS forest) of the graph. This forest has the following properties:

1. It contains all the vertices of the original graph $G$. Thus, the number of vertices in the forest is $V = 100$.
2. The number of connected components (trees) in the DFS forest is exactly equal to the number of connected components in the original graph $G$.

For any forest with $V$ vertices, $E_{\text{forest}}$ edges, and $C$ connected components, the relationship is given by:

Rearranging the formula to find the number of connected components $C$:

Substituting the given values:

Thus, the number of connected components in $G$ is 60.