Detect a Cycle in a Directed Graph
Oracle● MediumFULLTIMEPHONE SCREENProblem statement
Given n vertices numbered 0 through n - 1 and directed edges [u, v] from u to v, return whether the graph contains any directed cycle.
The graph may be disconnected. A self-loop counts as a cycle. Parallel edges are allowed and do not by themselves form a cycle.
Function
hasDirectedCycle(n: int, edges: int[][]) → booleanExamples
Example 1
n = 3edges = [[0,1],[1,2],[2,0]]return = trueThe edges form the directed cycle 0 to 1 to 2 to 0.
Example 2
n = 4edges = [[0,1],[0,2],[1,3],[2,3]]return = falseBoth paths merge at node 3, but no edge leads back to an ancestor.
Example 3
n = 3edges = [[2,2]]return = trueA self-loop is a directed cycle even in a disconnected component.
Constraints
0 <= n <= 100000.0 <= edges.length <= 200000.- Each edge has two valid vertex indices; when
n == 0, the edge array is empty.