Connected components
There are n machines numbered 0 to n - 1. Each item of edges is a two-way link [a, b] between two machines. Machines that can reach each other by following links, through other machines if needed, are in the same group. A group is as large as it can be: no machine outside it can be reached from inside it. A machine with no links is a group on its own. In graph words, a group is a connected component.
Return the number of groups.
n = 6, edges = [[0, 3], [3, 5], [1, 4]]Output3The groups are {0, 3, 5}, {1, 4} and {2}. Machine 2 has no links, so it is a group by itself.
n = 4, edges = [[0, 1], [1, 2], [2, 0], [2, 3]]Output1Every machine reaches every other one. The link [2, 0] closes a loop, so it joins nothing new.
n = 3, edges = []Output3No links: each machine is its own group.
1 ≤ n ≤ 105
0 ≤ len(edges) ≤ 105
Every link is [a, b] with 0 ≤ a, b < n and a ≠ b. No link is listed twice, in either order.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.