1016. The Biggest Group So Far
There are n members, each starting alone. Then q merges arrive, each a pair
u v putting the group holding u and the group holding v together.
After EVERY merge, print the size of the largest group that currently exists.
6 members, merges (1 2)(3 4)(5 6)(1 3) -> 2 2 2 4
4 members, merges (1 2)(1 2)(2 1) -> 2 2 2
5 members, merges (1 2)(2 3)(3 4)(4 5) -> 2 3 4 5
7 members, merges (1 2)(2 3)(4 5)(5 6)(6 7) -> 2 3 3 3 4
The last one is the shape to notice: a second group grows past the first, and the printed record changes owner without anything special being written for it.
## What most people try first
Recompute the group sizes after every merge, by walking all n members and tallying roots.
That is O(n alpha(n)) per merge and O(n q) in total, about 4 * 10^10 at the limits.
## The record only ever moves upwards, and only on a merge
Keep a size on every root, as in problem 992, and one extra number:
best = 1
for each merge (u, v):
if the union merged two different groups:
best = max(best, size of the new root)
print best
## Why comparing only the new group is enough
The sizes of every other group are unchanged by the merge, so the largest of them is still at
most best, which already holds the largest size ever seen. The only size that can have
risen is the one just formed, so comparing that single number against best is the whole
update.
It is also why best never falls: groups only ever join, so no size ever shrinks and the
running maximum is the current maximum.
## The two merges that must not change anything
u equal to v, and a pair already merged. Both give the same root twice, and the size
after such a merge is what it was before, so touching best would be harmless but adding one
to a size would not be. The second example is there precisely to catch a solution that adds
the sizes without checking the roots.
## The starting value
best starts at 1, not 0, because every member is already a group of one. On n = 1 with a
merge of a member with itself, the answer is 1 and a best of 0 prints 0.
## Overflow
Sizes never exceed n, which is 2 * 10^5, so nothing approaches the 2147483647 a signed
32 bit integer holds.
## Cross-reference
Problem 992 keeps the same size array and answers questions about a NAMED group instead of about the largest. Problem 367 prints the largest component of a FIXED graph by traversal, which is the right tool when nothing is asked twice and the graph never grows.
## Cost
Time O(n + q alpha(n)). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, and a pair may repeat.
Input
The first line contains two integers n and q.
Each of the next q lines contains two integers u and v.
Output
Print q lines. Line i holds one integer, the size of the largest group after the ith merge. Print the numbers alone, one per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.