Number of Connected Components in an Undirected Graph
Medium · Union Find · Depth-First Search · Breadth-First Search · Union Find · Graph
Problem
There are n nodes, numbered 0 to n - 1, and a list of undirected edges: [a, b] joins nodes a and b. Return the number of connected components, the groups of nodes that are joined to each other by paths and to nothing outside the group. A node with no edges is a component on its own.
An edge may be listed as [a, b] or [b, a], and no edge is listed twice.
Some tests have 20,000 nodes in one long chain, ten times LeetCode’s limit. A depth-first search that recurses from node to node goes 20,000 calls deep there and stops with RecursionError. Use union-find, or a search with a queue or an explicit stack.
Examples
Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2
Nodes 0, 1 and 2 form one component, and nodes 3 and 4 another.
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: 1
The edges chain all five nodes together.
Constraints
- 1 <= n <= 2 * 10^4 (LeetCode stops at 2,000)
- 0 <= len(edges) <= 5 * 10^4
- edges[i] == [a, b], 0 <= a, b < n, a != b
- no edge is listed twice, in either direction
Approaches
- Relabel whole components — time O(n · E), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
