Number of Connected Components in an Undirected Graph
The key idea
Start by treating every node as its own group. Each edge merges the two groups its endpoints belong to. Count how many distinct groups survive after all edges are processed.
Problem
You are given an integer n, the number of nodes in an undirected graph labeled from 0 to n - 1, and a list of undirected edges where each entry [a, b] means there is an edge between node a and node b. Return the number of connected components in the graph. A connected component is a maximal group of nodes such that every node is reachable from every other node in the group through some path of edges.
Constraints
- 1 <= n <= 2000
- 0 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= a_i <= b_i < n
- a_i != b_i
- There are no repeated edges.
Examples
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Complexity
Time: O(E * alpha(N)) Space: O(N)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization