1719. Give Every Vertex Its Group Number
A DIRECTED graph has n vertices and m arrows. Split the vertices into groups
of mutually reachable vertices, as problem 1717 counts them, and give every
vertex the NUMBER of its group. Print those numbers, one per vertex, for
vertices 1 to n in order.
The numbering has to be fixed or the answer is not unique, and the rule is chosen so that no algorithm is favoured:
sort the groups by their SMALLEST MEMBER, increasing
the group with the smallest smallest-member is group 1, the next is 2, ...
1->2, 2->3, 3->1, 3->4, 4->5 -> 1 1 1 2 3
1->2, 2->3, 3->4 -> 1 2 3 4
4 vertices, no arrows -> 1 2 3 4
2->3, 3->2, 1 alone -> 1 2 2
In the last example the groups are {1} and {2,3}, whose smallest members are
1 and 2, so vertex 1 is in group 1 and vertices 2 and 3 are both in group 2.
## Why the numbering rule matters
Problem 1718 prints the groups in the order Tarjan closes them, and Kosaraju closes them in the opposite order. Both are legitimate and they disagree, so a problem that asks for group NUMBERS and does not say how to number them has two different right answers. Sorting by smallest member is a property of the groups themselves, so every correct method lands on the same output.
## The three things that have to be said
directed? yes.
self-loops? allowed, and u -> u leaves u in a group of one.
parallel arrows? allowed, and they never merge two groups.
disconnected? allowed, and labels run across pieces, not within them.
## What most people try first
Printing whatever component index the chosen algorithm happened to hand out. That is the trap, and it is why this problem exists next to 1718: Kosaraju's pass-two counter numbers the groups in a topological order of the contracted graph, Tarjan's counter numbers them in the reverse, and neither matches sorting by smallest member. Any of the three can be turned into any other, but only after deciding which one is wanted.
## The method
compute the groups by either algorithm, obtaining comp[v] for every vertex
smallest[c] = min of the vertices with comp[v] == c
rank the groups by smallest[c], increasing; that rank plus one is the label
print label[comp[v]] for v = 1..n
The relabelling step is a sort of at most n numbers, so it costs
O(n log n) and changes nothing about the groups. Because every smallest[c]
is a distinct vertex number, the ranking has no ties to break, which is the
reason this rule is well defined where "sort by group size" would not be.
## Cost
Time O(n + m) for the groups plus O(n log n) for the relabelling. Space
O(n + m). The searches use an explicit stack, since a path of 200000 vertices
is permitted and recursion on it overflows Python's recursion limit and the
default stack in C, C++ and Java. Every printed label is at most n, so a
32-bit integer is plenty.
## Related
Problem 1717 counts the groups, problem 1718 orders them by when Tarjan closes them, and problem 1720 counts the arrows that survive once every group is squeezed to a point.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same arrow may be listed more than once - the graph may be disconnected
Input
The first line contains two integers n and m, the number of vertices and the number of arrows.
Each of the next m lines contains two integers u and v, an arrow FROM u TO v.
Output
Print one line holding n integers separated by single spaces: for each vertex from 1 to n in order, the number of the group it belongs to, where groups are numbered from 1 upwards in increasing order of their smallest member. Print nothing else.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.