Detect whether a directed graph given as an edge list contains a cycle

You are given a directed graph with n nodes labeled 0 to n - 1 and a list of directed edges. Return whether the graph contains at least one directed cycle.

Function Signature

def has_cycle(n: int, edges: list[list[int]]) -> bool:

edges[i] = [u, v] is a directed edge from node u to node v.

Rules

• A directed cycle is a path of one or more edges that follows edge directions and returns to the node it started from.
• A self-loop [u, u] is a cycle of length one.
• The same edge may appear more than once. Two copies of the edge from u to v do not form a cycle by themselves.
• The graph may be disconnected, and some nodes may have no edges at all.
• Return True if at least one directed cycle exists anywhere in the graph, otherwise False.

Constraints

• 1 <= n <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• 0 <= u <= n - 1 and 0 <= v <= n - 1 for every edge [u, v]

Examples

Example 1

Input: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: False

Node 3 can be reached from node 0 along two paths, 0 -> 1 -> 3 and 0 -> 2 -> 3, but no path ever leads back to a node it has already passed through.

Example 2

Input: n = 5, edges = [[4, 0], [0, 1], [1, 2], [2, 3], [3, 1]]
Output: True

The edges 1 -> 2, 2 -> 3 and 3 -> 1 form a cycle.

Example 3

Input: n = 2, edges = [[0, 1], [1, 1]]
Output: True

The self-loop on node 1 is a cycle of length one.