1728. How Early Can the Search Climb Back
An UNDIRECTED graph has n vertices and m edges. Run a depth-first search
over it and print, for every vertex, two numbers: the time it was ENTERED, and
the earliest entry time its subtree can climb back to.
The second number is called the LOW-LINK value, and everything in the next few problems is built on it.
So that there is exactly one correct answer, the search is pinned:
start a new search at the smallest vertex not yet entered
from a vertex, take its edges in increasing order of the other endpoint,
and among several edges to the same vertex in the order they were listed
entry times are 1, 2, 3, ... in the order vertices are entered
``` edges 1-2, 2-3, 3-1 vertex 1: tin 1 low 1 vertex 2: tin 2 low 1 vertex 3: tin 3 low 1
edges 1-2, 2-3 vertex 1: tin 1 low 1 vertex 2: tin 2 low 2 vertex 3: tin 3 low 3 ```
## What low-link actually means
low[v] = the smallest entry time of any vertex reachable by starting at v,
walking DOWN the search tree as far as you like, and then taking at
most ONE edge that is not the edge you came into that vertex by
In the triangle, vertex 3 can take the edge back to vertex 1, whose entry time
is 1, so low[3] = 1. In the path, vertex 3 has only the edge it arrived by, so
it can reach nothing earlier and low[3] = tin[3].
## The three things that have to be said
directed? no. Every edge can be walked both ways, which is why the
edge you arrived by has to be excluded by hand.
self-loops? allowed. An edge from v to v is skipped: it reaches nothing
but v, whose entry time is already low[v]'s starting value.
parallel edges? allowed, and they matter. Only the SINGLE EDGE the search
arrived by is excluded, so a second copy of that edge is a
genuine way back and does lower the value.
disconnected? allowed. The search restarts at the smallest vertex not yet
entered, and the clock keeps running across restarts.
## What most people try first
Excluding the parent VERTEX rather than the parent EDGE. On a graph with two
copies of the edge 1-2 that is wrong: the second copy is a real way back from
2 to 1, so low[2] should be 1, and excluding the vertex gives 2. There is a
test below that is exactly that graph, and this single distinction is what makes
the next problem's answer come out right on multigraphs.
## Maintaining it during the search
enter v: tin[v] = low[v] = clock++
for each edge (v, w) other than the one v arrived by, and with w != v:
if w has not been entered: descend, and afterwards low[v] = min(low[v], low[w])
else: low[v] = min(low[v], tin[w])
Why those two cases are complete and correct. If w is unentered, the search
goes there, and everything w's subtree can climb back to is also reachable
from v through w, so folding in low[w] is right and nothing is missed. If
w has been entered, the edge (v, w) is itself the "at most one" edge, so
tin[w] is what it offers, and low[w] must NOT be used: low[w] may include
a second non-tree edge further along, which would be two such edges in one walk
and is not what the definition allows.
That last sentence is the whole reason the second case says tin and not low,
and using low there is the most common way to get a wrong answer that still
looks plausible on small trees.
## Cost
Time O(n + m log m): the search is linear and the sort of the incidence lists,
which only the pinned order needs, is the rest. Space O(n + m). Build the
search ITERATIVELY with an explicit stack and a per-vertex index into its edge
list: 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. The fold
low[v] = min(low[v], low[w]) then has to happen when w is POPPED, since
there is no return from a call to do it on.
## Related
Problem 1729 counts the bridges from these numbers, problem 1732 the cut vertices, and problem 1718 computes the same kind of value on a DIRECTED graph, where "still on the stack" replaces "not the edge I came by".
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same pair may be listed more than once, so parallel edges can occur - the graph may be disconnected
Input
The first line contains two integers n and m, the number of vertices and the number of edges.
Each of the next m lines contains two integers u and v, an undirected edge joining u and v. The edges are numbered 1 to m in the order they are listed, which is the order the pinned search uses to break ties.
Output
Print n lines. Line v holds two integers separated by a single space: the time vertex v was entered, and its low-link value, both under the pinned search described above. Print nothing else.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.