FunctionRacerProblemsRace

Groups After Each Merge

EasyGraphsPython, JavaScript, TypeScript, Java, C++

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

n 5
merges [[0,1],[2,3],[1,3],[0,2]]
returns [4,3,2,2]

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

n 3
merges [[1,1],[0,2]]
returns [3,2]

Merging 1 with itself changes nothing (still three groups); merging 0 and 2 leaves two.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems