Number of Connected Components in an Undirected Graph
Medium
graphs
union-find
The graph has n nodes, labeled 0 to n - 1. Each pair [a, b] in edges joins nodes a and b, and the connection works in both directions.
Return the number of groups. Two nodes belong to the same group when a path of edges leads from one to the other. A node with no edges is a group of its own.
Example 1
Input
n = 6, edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Output
3
Explanation
the groups are {0, 1}, {2, 3, 4} and {5}. Nodes 2, 3 and 4 are joined in a triangle, and that is still one group. Node 5 has no edge.
Example 2
Input
n = 4, edges = []
Output
4
Explanation
with no edges every node stands alone.
Constraints:
0 <= a, b < n for every pair [a, b] in edges
Tab indents. Press Esc, then Tab to leave the editor.
Ctrl or ⌘ + Enter runs the tests.
Run your code to see every test here. Nothing is submitted or recorded.