186. Count Connected Components in an Undirected Graph

Given an undirected graph with n vertices and m edges, count the number of connected components (an isolated vertex with no edges counts as its own component).

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers, an undirected edge. Output: Print a single integer - the number of connected components.

1 <= n <= 10^5

An ISOLATED vertex with zero edges still counts as its OWN separate component - a small but important detail explicitly called out in this problem's own statement.

Count how many separate, disconnected groups (components) a graph splits into. Brute force: Check every pair of vertices directly for reachability - this costs O(n²) or worse, far more than necessary when a single BFS/DFS sweep answers the question directly. Optimised: Since one BFS/DFS run from any vertex reaches EXACTLY its entire connected component, repeating this only from vertices not yet covered by a previous run visits every vertex exactly once overall, with the number of times you START a fresh run being exactly the component count.

Represent the graph as an n x n adjacency matrix, so finding a vertex's neighbors during a traversal requires scanning its entire matrix row. Running a DFS or BFS from every unvisited vertex this way still correctly finds every component, but each neighbor lookup costs O(n) instead of being handed directly from an adjacency list. Time: O(n^2) Space: O(n^2)

Use a Disjoint Set Union structure with path compression and union by rank/size: start with n separate sets, then union the sets containing each edge's two endpoints for all m edges. The final number of distinct set representatives (roots) is the answer. This avoids recursive or stack-based traversal entirely, eliminating any risk of stack overflow on deep graphs, and each union/find operation runs in near-constant amortized time. Time: O((n + m) * alpha(n)) Space: O(n)

Build an adjacency list from the m edges, then repeatedly pick any unvisited vertex, run a DFS or BFS from it to mark every vertex reachable from it, and increment a component counter each time a new search is started. Using an adjacency list means each edge is examined only a constant number of times overall rather than paying O(n) per neighbor lookup, so the traversal cost drops to the size of the graph itself. Time: O(n + m) Space: O(n + m)

1. Run a BFS or DFS from every vertex that HASN'T been visited yet. 2. Every vertex reached during that traversal gets marked visited. 3. Each time you START a fresh traversal from an unvisited vertex, that's one more connected component.

Time: O(n + m) - every vertex and edge is examined exactly once across all the BFS/DFS runs combined. Space: O(n), for the visited-tracking array.

Test m = 0 (every vertex is its own component, so the answer equals n), a fully connected graph (answer 1), and n at the upper bound of 10^5.

Be ready to mention Union-Find (Disjoint Set) as an equally valid alternative approach - processing all edges with union operations and counting the final number of distinct sets gives the same answer, often preferred when edges arrive incrementally.