Number of Connected Components in an Undirected Graph medium
Description
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] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i.
Return the number of connected components in the graph.
Examples
> Case 1:
n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
> Case 2:
n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1Constraints
1 <= n <= 20001 <= edges.length <= 5000- No repeated edges, no self-loops.
State design
Five-line DSU. Start with n components. Every successful union decrements the counter. Return it at the end.
Code
Analysis
- Time:
O((V + E) · α(V)). - Space:
O(V).
This is the prototype DSU problem. Internalize this exact shape — it appears, subtly modified, in two-thirds of the practice list.
Same skin
- Number of Provinces — matrix instead of edge list.
- Graph Valid Tree — add cycle and exactly-one-component checks.
- Number of Islands — grid version; DFS is more common but DSU works.