1703. The Order Depth First Search Finishes In

A DIRECTED graph with n vertices and m arrows is given and is guaranteed to have NO directed cycle. Produce a topological order by depth first search, using exactly this rule so that the answer is unique:

for s = 1, 2, ..., n: if s has not been visited, start a depth first search at s at each vertex, try its out-neighbours in INCREASING numeric order append a vertex to a list when it FINISHES, after all its out-neighbours reverse the list and print it

4 vertices, arrows 1->2, 1->3, 2->4, 3->4 -> 1 3 2 4

Follow it: from 1 go to 2, from 2 go to 4, 4 finishes, 2 finishes, back at 1 go to 3, whose only neighbour 4 is already visited, so 3 finishes, then 1 finishes. The finish list is 4 2 3 1 and reversed it is 1 3 2 4.

## The three things that have to be said

directed? yes. self-loops? impossible. A self-loop is a cycle, and the input is acyclic. parallel arrows? allowed. The second copy finds its head already visited. disconnected? allowed, which is why the outer loop restarts at every s.

## What most people try first

Printing the order vertices are FIRST REACHED in, rather than the order they FINISH in. It is the same traversal with the append moved three lines up, and it is wrong. On 1->3, 2->3 reaching order is 1 3 2, which puts 3 before 2 while the arrow 2->3 demands the opposite. Finishing order reversed gives 2 1 3, which does not.

## Why reversed finishing order is a topological order

Take any arrow u -> v and ask when each endpoint finishes.

When the search is standing at u and looks at v, exactly one of two things is true.

Either v has not been visited, in which case the search goes there now and v finishes before the search returns to u, so v finishes first.

Or v has been visited already. It cannot still be unfinished: an unfinished visited vertex is one the search is currently inside, which would mean a route from v back to u, which with the arrow u -> v is a directed cycle, and there are none. So v is finished, and again v finishes before u.

Either way v finishes strictly before u for every arrow u -> v. Reversing the finish list therefore puts u before v for every arrow, which is the definition of a topological order.

Notice what carried the argument: the absence of a cycle is exactly what rules out the third case. The same observation, used the other way round, is how a directed cycle is detected in problem 1712.

## Build the stack yourself

The constraints allow a path of 200000 vertices, which recurses 200000 deep. That exceeds Python's default limit of 1000 outright and overflows the default stack in C, C++ and Java. So the reference solutions keep an explicit stack of (vertex, how many of its neighbours have been tried) pairs and append on pop. That is not a stylistic preference; the shape is permitted by the constraints.

## Cost

Time O(n + m + sum of degree log degree) for the sorting of each vertex's neighbour list, which is O(n + m log m) in the worst case. Space O(n + m) for the adjacency list, which the constraints force; an adjacency matrix would be 4 * 10^10 entries at n = 2 * 10^5. Nothing overflows.

## Related

Problem 380 prints the LEXICOGRAPHICALLY SMALLEST topological order, which needs Kahn's algorithm with a priority queue. This prints a different order produced by a different algorithm, and the two agree only by coincidence. Problem 1709 asks whether a graph has just one order, in which case they must agree.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - the graph has no directed cycle, so no self-loop can occur - the same arrow may be listed more than once - the graph may be disconnected