1712. Show Me the Cycle
A directed graph of n vertices and m arrows is given. If it contains a
cycle, print the vertices of one cycle in the order they are visited. If it
contains none, print None.
A self-loop, an arrow from a vertex to itself, is a cycle of length 1.
1->2 2->3 3->1 -> 1 2 3
1->2 2->3 3->4 4->2 -> 2 3 4
1->2 2->3 -> None
1->1 -> 1
## Which cycle, exactly
A graph may hold many cycles, so the answer is only well defined once the search is pinned. Print the cycle found by a depth-first search that
- starts from the smallest vertex not yet visited, and
- explores each vertex's out-arrows in increasing order of destination,
printing the current search path from the repeated vertex onward. Every test below follows that rule.
## What most people try first
Detecting a cycle and printing a word, which problem 1704 already does. The step from a yes-or-no answer to the witness is where the work is: a counter of finished vertices proves a cycle exists and keeps no record of where it is.
The next attempt marks vertices "visited" and reports a cycle when a visited one
is reached again. That is wrong, and the reason matters. Reaching an
already-visited vertex means only that it was seen before, not that it is on the
CURRENT path. On 1->2, 1->3, 2->4, 3->4 the search reaches 4 twice and the
graph has no cycle at all.
## Three colours, not two
Give every vertex one of three states:
white not yet reached
grey on the current search path, entered but not finished
black finished, along with everything reachable from it
A cycle exists exactly when the search follows an arrow into a GREY vertex. An arrow into a black vertex is harmless: everything below it is already explored and contained no cycle.
dfs(x):
colour[x] = grey
for y in sorted(out-arrows of x):
if colour[y] == grey: the path from y to x, plus y, is the cycle
if colour[y] == white: dfs(y)
colour[x] = black
## Recovering the cycle, not just detecting it
Keep the current path on a stack as the search descends, popping on the way out.
When an arrow reaches a grey vertex y, that y is somewhere on the stack, and
everything from y up to the top is the cycle, in order.
The stack is what turns the detection into a witness, and it is also why the grey state alone is not enough: grey tells you a cycle exists, the stack tells you which one.
## The boundaries
A self-loop makes the cycle a single vertex, and the arrow is from grey straight back to the same grey vertex, so the stack slice is one element long. A graph whose only cycle is unreachable from vertex 1 is why the outer loop restarts at every unvisited vertex; the test with the cycle between 2 and 3 while 1 points at both exists for that.
Build the search ITERATIVELY. A path of 200000 vertices is permitted by the constraints and overflows Python's recursion limit and the default stack in several other languages.
## Cost
O(n + m) for the search, plus O(m log m) if the out-arrows are sorted to
make the choice deterministic. Each vertex is entered once and each arrow
examined once.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - self-loops and repeated arrows are allowed - the graph may be disconnected
Input
The first line contains two integers n and m.
Each of the next m lines contains two integers u and v, an arrow FROM u TO v. A self-loop with u equal to v is allowed, and the same arrow may appear more than once.
The graph may be disconnected.
Output
Print the vertices of one cycle on a single line, separated by single spaces, in the order the search visits them and starting at the repeated vertex, without repeating that vertex at the end. If the graph has no cycle, print the single word None.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.