Directed Graph Cycle Detection II

Given a directed graph, return true if the graph contains a cycle. Pattern focus: Cycle Detection. The same recursion-state idea used in topological sort can directly prove whether the graph is a DAG.

Input Format

n = number of vertices, edges = directed edge list

Output Format

true if the graph contains a directed 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...
Directed Graph Cycle Detection II