Reverse Disjoint Union Set | Reverse Union Find

You have recently been promoted as the director of infrastructure at Algo Monster. Congratulations! Your new task is to destruct all the roads that connect cities in the province so that they can be rebuilt in the future.

Your are asked to destruct the roads in order as they appeared in the input. Your collegue wants to know how many clusters of cities are in the province after each road destruction.

Two cities are considered to be in the same cluster when there exist (at least) a path between the two using the remaining roads. That is, if you can travel from city A to city B, then city A is in the same cluster as city B.

The input consists a number n indicating the total number of cities in the province, and a list of all the roads in the province breaks, where each road is represented as a two integer list, i.e. [1,2] represents a road connecting city 1 and city 2. Then, you have to destruct these roads in the order as it appears in the input, and output the number of clusters after you destroy each road as a integer list.

Examples

Example 1:

Input: n = 4, breaks = [[1, 2], [2, 3], [3, 4], [1, 4], [2, 4]]
Output: [1, 1, 2, 3, 4]
Explanation:

Try it yourself

Solution