Detect Cycle in Directed Graph

Given a directed graph with vertices numbered from 0 to n-1, return true if the graph contains a directed cycle. Pattern focus: Only valid on DAGs. A topological sort exists only when the graph has no directed cycle.

Input Format

n = number of vertices, edges = directed edge list

Output Format

true if the graph contains a cycle

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9

Examples

Example 1:

Input:

n = 4
edges = [[0,1],[1,2],[2,0],[2,3]]

Output:

true

Explanation:

The path 0 -> 1 -> 2 -> 0 forms a directed cycle.

Example 2:

Input:

n = 3
edges = [[0,1],[1,2]]

Output:

false

Explanation:

A simple chain has no cycle.

Example 3:

Input:

n = 2
edges = [[0,1]]

Output:

false
Loading...
Detect Cycle in Directed Graph