Number of Connected Components
You are given n nodes labelled 0..n-1 and a list of undirected edges. Return the number of connected components in the graph.
- 1 ≤ n ≤ 2000
- 0 ≤ edges.length ≤ 5000
- No duplicate edges
- Edges given as a list of pairs rather than an adjacency structure
- "How many groups" — merging sets
- Each edge either joins two groups or is redundant
When connectivity is built up incrementally by unions and queried repeatedly, disjoint sets with path compression and union by rank answer both in near-constant amortized time, without rebuilding anything. It is the right tool whenever DFS would have to be rerun after each new edge, and it is the engine of Kruskal's MST.
Initialise a disjoint-set structure with n singleton sets and a component counter equal to n. For each edge, find the roots of both endpoints; if they differ, union them and decrement the counter. With path compression and union by rank each operation is effectively constant, and the final counter is the number of components.
- Build an adjacency list and count how many times a DFS/BFS must be started from an unvisited node — O(n + e), and the natural choice if you need the members of each component.