1013. The Links Going Down One by One

A system has n machines and m links, all present at the start. The links are then CUT one at a time, in the order listed. A link may join a machine to itself, and the same pair may be linked more than once, in which case cutting one copy leaves the other.

Print m + 1 numbers, one per line: the number of separate parts before any cut, then after the first cut, and so on up to after the last cut.

4 machines, cut order (1 2)(2 3)(3 4) -> 1 2 3 4 3 machines, cut order (1 2)(2 3)(3 1) -> 1 1 2 3 2 machines, cut order (1 2)(1 2) -> 1 1 2 4 machines, no links -> 4

The second one is worth checking. The three links form a triangle, so cutting the first leaves a path and nothing separates. Only the second cut breaks something.

## A disjoint set cannot do this directly, and that is the point

The structure supports exactly one change: putting two groups together. There is no operation that takes a merge back. Once two roots have been joined, the information about which elements came from which side is gone, deliberately, because throwing it away is what makes the structure fast.

So no amount of cleverness will let you cut a link and ask the same structure for the new count. The options are to give up the structure, or to give up the order.

## What most people try first

Traverse the whole system after every cut. Each traversal is O(n + m) and there are m + 1 of them, so at the limits that is about 6 * 10^10 steps.

The other attempt is to keep a count and raise it whenever a cut disconnects something. That needs to know whether the cut link was a BRIDGE, which is a genuinely harder question than the one being asked, and it changes after every cut.

## Run time backwards

Read all the cuts first. Then start from the end, with NO links at all, and put them back in reverse order. Putting a link back is a merge, which is exactly what the structure does.

read the links into an array parts = n result = [parts] the state after every link has been cut for i from m-1 down to 0: if union(links[i]) merged: parts = parts - 1 append parts to result reverse result and print it

## Why reversing gives the right answers

After the first i cuts the system holds exactly the links i+1 .. m. The reverse sweep, having added links m, m-1, ... , i+1, holds exactly the same set, so its count is the count after i cuts. Reading the recorded counts backwards lines them up with i = 0, 1, ... , m.

Nothing about the counts depends on the ORDER links were added in, only on which links are present, which is what makes the reversal legitimate.

## The price of the reversal

The whole input has to be read before any answer can be produced. That is fine for a file and is impossible for a live stream, and it is the honest cost of the trick: a problem that must answer as the cuts happen cannot use it at all, and needs a genuinely harder structure that supports deletion.

## The repeated link

Two links between the same pair are two separate objects. Cutting the first changes nothing because the second still joins the machines. In the reverse sweep that falls out on its own: adding the second copy merges two groups and adding the first merges nothing.

## Cross-reference

Problem 793 also loses cells over time and solves it a different way, by binary searching for the last moment a crossing survives; its statement names this reverse sweep as the other accepted method and does not use it. Problem 991 runs the same counter forwards, which is what this problem cannot do.

## Cost

Time O((n + m) alpha(n)). Space O(n + m).

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, and a pair may be linked more than once.