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.
