Groups After Each Merge
There are n clubs numbered 0 to n - 1, and at first every club is a group of its own. merges is a list of pairs [a, b] that are carried out in order: the group containing club a and the group containing club b become one group. If the two clubs are already in the same group (including when a == b), nothing changes.
Return a list with one entry per merge: the number of groups right after that merge has been carried out. Return [] when merges is empty.
Example 1
Five groups become four, then three, then two; the last merge joins 0 and 2, which are already together, so it stays at two.
Example 2
Merging 1 with itself changes nothing (still three groups); merging 0 and 2 leaves two.
Constraints
1 <= n <= 500 <= len(merges) <= 1000 <= a, b <= n - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.