Storm footbridges
MediumOnline Assessment
Track how an archipelago falls apart as a storm destroys its footbridges one by one.
An archipelago has n islands numbered 0 to n - 1. Footbridges connect some pairs of islands, and every bridge can be walked in both directions. You are given bridges, a list of [a, b] pairs, in the order the storm will destroy them: the bridge at index 0 collapses first, then the one at index 1, and so on, until every bridge is gone.
Two islands are in the same group if you can walk from one to the other using only bridges that are still standing (an island with no standing bridge is a group by itself). Two different bridges may join the same pair of islands; each collapses on its own schedule, and the pair stays connected for as long as at least one of them stands.
After each collapse, report the number of islands in the largest group.
Input: n, the number of islands, and bridges, the list of bridges in collapse order.
Output: a list with one integer per bridge: element i is the size of the largest group right after bridge i has collapsed (so bridges 0..i are gone and the rest still stand). If there are no bridges, return an empty list.
Archipelagos can have thousands of bridges, so recomputing the groups from scratch after every collapse will be too slow.
Example 1
- Input:
- [4,[[0,1],[1,2],[2,3]]]
- Output:
- [3,2,1]
- Explanation
- The bridges form a chain 0-1-2-3. After the first collapse the standing bridges are 1-2 and 2-3, so the largest group is {1, 2, 3}: 3 islands. After the second only 2-3 is left, so the best group has 2 islands. After the third, nothing stands and every group is a single island.
Example 2
- Input:
- [5,[[0,1],[1,2],[0,1],[3,4]]]
- Output:
- [3,2,2,1]
- Explanation
- There are two separate 0-1 bridges. When the first collapses, the second still joins islands 0 and 1, so {0, 1, 2} is still one group of 3. After 1-2 collapses the groups are {0, 1} and {3, 4}: 2. After the second 0-1 bridge collapses, only 3-4 remains: 2. After the last collapse: 1.
Example 3
- Input:
- [4,[[0,1],[1,2],[2,0],[2,3]]]
- Output:
- [4,3,2,1]
- Explanation
- Islands 0, 1, 2 form a loop, so losing one of its bridges does not split anything: after the first collapse bridges 1-2, 2-0 and 2-3 still join all four islands (4). After the second, 2-0 and 2-3 leave {0, 2, 3} (3). After the third only 2-3 stands (2), and after the fourth everything is alone (1).
Constraints
1 <= n <= 20,0000 <= bridges.length <= 3,000- each bridge is
[a, b]with0 <= a, b < nanda != b; the same pair of islands may appear more than once, in either order