A graph has n nodes, numbered 0 to n - 1. Each edges[i] = [a, b] is an undirected link between node a and node b.
A connected component is a group of nodes that can all reach one another along the edges, and that no node outside the group can reach. A node with no edges is a component on its own.
Return how many connected components the graph has.
The groups are {0, 1}, {2, 3, 4} and {5}. Node 5 has no edges, so it counts by itself.
Every node links to node 3, so all four are in one group.
The loop 0 – 1 – 2 is still a single group. Nodes 3 and 4 are one group each.
Constraints
1 <= n <= 20001 <= edges.length <= 5000edges[i].length == 20 <= a < b < n for each edges[i] = [a, b]Every edge that joins two nodes from different groups merges those groups, so the number of groups drops by one. An edge inside a group changes nothing.
Picture the n nodes before any edge is drawn: n pieces, one node each. Now draw the edges one at a time and watch the count.
Time O(n + m log n)Space O(n)
The full walkthrough and code are part of Premium
3