Reverse Disjoint Union Set | Reverse Union Find

You are the new Director of Infrastructure at Algo Monster. Your primary task is to systematically dismantle the roads connecting cities in a province, with plans for future reconstruction.

Follow this procedure:

Dismantle the roads in the sequence provided in the input. After dismantling each road, calculate and record the number of city clusters remaining. A "cluster" is defined as a group of cities where it's possible to travel between any two cities within that group using the roads that remain. For example, if there's a path from city A to city B using existing roads, then A and B are in the same cluster.

Input:

A number 'n', representing the total number of cities. A list detailing the roads to be dismantled. Each road is shown as a pair of integers. For instance, [1,2] means there's a road between city 1 and city 2. Output:

A list of integers showing the number of city clusters after each road is dismantled.

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

←
↑TA πŸ‘¨β€πŸ«