Find a cycle

A directed graph has vertices 0 to n − 1, and each edge (u, v) goes one way, from u to v. If the graph has a cycle (a route that follows edges and comes back to where it started), return one, as a list of different vertices [v0, v1, …, vk] where each vertex has an edge to the next, and the last has an edge back to the first. Otherwise return None.

edges = [(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)]
find_cycle(5, edges)                  # [1, 2, 3]
diamond = [(0, 1), (0, 2), (1, 3), (2, 3)]
find_cycle(4, diamond)                # None
find_cycle(2, [(0, 1), (1, 1)])       # [1]

Any cycle is accepted, starting from any of its vertices. An edge from a vertex to itself is a cycle of one vertex. The tests follow your cycle’s edges to check it.

Limits

• Up to 100,000 vertices and 200,000 edges.
• Paths can be 100,000 vertices deep, so use your own stack (as in P3). One test has 2⁴⁰ different paths: each vertex must be searched only once. The big tests have 3 seconds each.