GATE CS 2008 Q7 — Asymptotic Worst Case Time and Space Complexity

The number of connected components in an undirected graph can be determined using standard graph traversal algorithms such as Depth-First Search (DFS) or Breadth-First Search (BFS).

When the graph is represented using an adjacency list:

• We initialize a counter for connected components to $0$ and keep track of visited vertices.
• We iterate through all $n$ vertices. If a vertex is not yet visited, we increment our counter and start a DFS/BFS traversal from that vertex to mark all reachable vertices in its component as visited.
• The traversal visits every vertex and explores every edge incident to it.

The time complexity of this approach is:

where $n$ is the number of vertices and $m$ is the number of edges. This is asymptotically optimal because any algorithm must, in the worst case, examine every vertex and edge to correctly identify all components.

Therefore, the correct option is C.