Cycle Detection in a Directed Graph

Detect whether a directed graph contains a cycle.

graph dfs cycle

Write a function `has_cycle(n: int, edges: list[list[int]]) -> bool` that returns `True` if a directed graph with `n` nodes (labeled `0` to `n-1`) contains a cycle, and `False` otherwise.

You are given `edges`, a list of directed edges `[u, v]` meaning `u -> v`. The graph may be disconnected (multiple components). Implement cycle detection using any algorithm (e.g., DFS with a recursion stack or Kahn's algorithm).

Constraints

- `1 <= n <= 1000`
- `0 <= len(edges) <= 5000`
- `0 <= u, v < n`
- Edges may contain duplicates.
- The graph may have self-loops (an edge from a node to itself).

Example

>>> has_cycle(2, [[0,1]])
False
>>> has_cycle(2, [[0,1],[1,0]])
True
>>> has_cycle(3, [[0,1],[1,2],[2,0]])
True
>>> has_cycle(1, [[0,0]])
True

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Represent the graph as a list of adjacency lists for each node.

Use three states: unvisited (0), visiting (1), and visited (2) to detect a back edge.

A back edge occurs when you encounter a node that is currently in the 'visiting' state during DFS.

IF the graph is disconnected, run DFS from every unvisited node.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.