Connected components in a graph

Given an undirected graph, count the number of connected components and be able to list the members of each. A component is a maximal set of vertices mutually reachable from one another.

Input / Output

• Input: number of nodes n and a list of undirected edges [u, v].
• Output: the count of connected components (be ready to also return the members of each).

Constraints

• 1 <= n <= 10^5
• 0 <= edges.length <= 2 * 10^5
• The graph may be disconnected and contain isolated vertices.

Example

• n = 5, edges = [[0,1],[1,2],[3,4]] → 2 components: {0,1,2} and {3,4}.

Expected approach

• Build an adjacency list, then run DFS/BFS from each unvisited node, incrementing the count once per traversal; or
• Use Union-Find (disjoint set) with path compression and union by rank, then count distinct roots.
• O(n + e) with DFS/BFS; near O((n + e)·α(n)) with Union-Find.