Finish order

A directed graph is given as adjacency lists: adj[u] lists the vertices that u has an edge to, in order. Run a depth-first search exactly as the recursive version in lesson 3 would: start at vertex 0, try the neighbours of each vertex in the order of its list, and when the search from 0 is over, start again from the smallest vertex not yet visited.

A vertex finishes when every neighbour in its list has been tried. Return the vertices in the order they finish.

finish_order([[1, 2], [3], [3], []])   # [3, 1, 2, 0]
finish_order([[2, 1], [3], [3], []])   # [3, 2, 1, 0]
finish_order([[1], [], [0], []])       # [1, 0, 2, 3]

In the first example, 0 goes to 1 and 1 goes to 3. Vertex 3 has no neighbours, so it finishes first, then 1. Back at 0, the next neighbour is 2; its only neighbour, 3, is already visited, so 2 finishes, and then 0.

Limits

• Up to 100,000 vertices and 300,000 edges. Lists may contain a vertex itself, or the same neighbour twice.
• Paths can be 100,000 vertices deep. A recursive function fails: Python stops at about 1,000 nested calls, and the browser may stop sooner. Keep your own stack. The big tests have 3 seconds each.