DSA problem
Number of Connected Components in an Undirected Graph
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph. Return the number of connected components in the graph.
This is the canonical Union Find problem: detect and count connected components of an undirected graph. We start with every node in its own component (giving n components total), then process each edge in order. Whenever an edge (u, v) successfully merges two previously-separate trees, the total component count decrements by one.
The DSU operates in two key methods: find with path compression to flatten the tree on the way up, and union with union by rank to keep the trees shallow. Each operation runs in amortised inverse-Ackermann time, which is effectively constant for any input you would encounter in practice.
The total complexity is O((n + e) * alpha(n)) time and O(n) extra space, where e is the number of edges. This problem also has a DFS solution (see the DFS category), but the DSU formulation is shorter, requires no adjacency list, and reuses the standard DSU template that is foundational across all Union Find problems.
Examples
n = 5, edges = [[0,1],[1,2],[3,4]]2n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]1n = 4, edges = []4Constraints
- 1 <= n <= 2000
- 1 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= ai <= bi < n
- ai != bi
- There are no repeated edges.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.