There are n nodes, numbered from 0 to n − 1, and a list edges where each [a, b] joins
nodes a and b (edges have no direction). Two nodes are in the same group if you can get from
one to the other along edges.
Return the number of groups (the connected components). A node with no edges is a group on its own.
Example 1
- Input
- n = 6, edges = [[0, 3], [3, 4], [1, 5]]
- Output
- 3
Example 2
- Input
- n = 4, edges = [[0, 1], [1, 2], [2, 0], [2, 3]]
- Output
- 1
Constraints
- 1 ≤
n≤ 2000 edgesholds 0 to 5000 edges. Each joins two different nodes, and no edge is listed twice.
Show the pattern
Union-find, Graphs
The edges arrive as a list, and each one may merge two groups into one. Union-find starts with every node in a group of its own and merges groups as edges come in; each real merge leaves one group fewer.
See union-find in a visualiserShow the approach
Union-find. Give each node a parent, starting with itself, so every node is the root of its own
group. find(x) follows parent links to the root of x's group, pointing nodes closer to the root
as it goes (path compression) so later finds are quick.
Start the count at n. For each edge, find the roots of both ends. If they differ, link one root
under the other and subtract one from the count; if they are the same, the edge joins two nodes
that were already connected and changes nothing. The count left at the end is the number of
groups.
Counting the breadth-first or depth-first searches needed to visit every node works as well.
Time: O(n + E · log n), close to linear in practice · Space: O(n)