993. The Smallest Member of Each Group
There are n members, each starting alone, and m lines each joining two of them
into one group.
For every member from 1 to n, print the SMALLEST number in that member's group, all on one
line.
6 members, joins (2 3) (4 5) (5 6) -> 1 2 2 4 4 4
4 members, no joins -> 1 2 3 4
5 members, joins (5 4)(4 3)(3 2)(2 1) -> 1 1 1 1 1
7 members, joins (7 1) (6 2) (5 3) -> 1 2 3 4 3 2 1
## The root is not the answer
The obvious idea is to print find(i), since every member of a group has the same root. It
gives a consistent labelling, which is not what was asked, and it is almost never the
smallest member. Which element ends up as root depends on the merge order and on whichever
tie-breaking rule the size comparison happens to use, so the same input can produce different
roots in two correct implementations.
Look at the third example. Joining 5 and 4 makes one of them root; by the end, with union by size, the root of the whole group can easily be 5, and 5 is the LARGEST member.
## Two passes
The root is still the right key. Take a minimum over it.
for i in 1 .. n:
lo[i] = i
for i in 1 .. n:
r = find(i)
lo[r] = min(lo[r], i)
for i in 1 .. n:
print lo[find(i)]
## Why this is correct
After all merges, find is constant on a group and different across groups, so grouping
members by their root partitions them exactly as the joins do. The second pass therefore
visits every member of a group exactly once while accumulating into that group's root, so
lo[r] ends as the minimum over the whole group. The third pass reads it back through the
same key.
## The trap in trying to do it in one pass
Setting lo[find(i)] = min(lo[find(i)], i) and printing in the same loop prints an answer
for member 1 before members 2 to n have been examined. That is fine here only because the
loop runs upwards and the minimum of a group is seen first, which is luck rather than
reasoning, and it breaks the moment the loop order changes. Two passes are honest.
## A cheaper variant, and why it is not used here
You can force the smaller root to survive every merge, by writing if ru > rv: swap instead
of comparing sizes. Then find(i) IS the smallest member and one pass is enough. The price
is giving up union by size, which is what keeps the trees shallow, so the structure degrades
to O(log n) per operation with path compression alone rather than O(alpha(n)). At this
size either is fine; the two-pass version is written out because it keeps the two concerns
apart.
## Cross-reference
Problem 1028 does exactly this over the 26 letters and then uses the labels to rewrite a word, which is where the minimum stops being an arbitrary choice and becomes the answer. Problem 994 keeps the whole group rather than one number from it.
## Cost
Time O((n + m) alpha(n)). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, and a pair may repeat.
Input
The first line contains two integers n and m.
Each of the next m lines contains two integers u and v, two members to join.
Output
Print one line holding n integers separated by single spaces: for each member from 1 to n in order, the smallest number in that member's group.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.