FastPrepDetect a Cycle in a Directed Graph
Problem · Graph

Detect a Cycle in a Directed Graph

Learn this problem
● MediumMakeMyTrip.com logoMakeMyTrip.comFULLTIMEONSITE INTERVIEW

Problem statement

Given n vertices numbered from 0 to n - 1 and a list of directed edges, return whether the graph contains at least one directed cycle.

Function

hasDirectedCycle(n: int, edges: int[][]) → boolean

Examples

Example 1

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

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

Example 2

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

No directed path returns to an active ancestor.

Constraints

  • 1 <= n <= 100000
  • 0 <= edges.length <= 200000
  • Every edge contains two valid vertex indices.
  • Parallel edges may appear.

More MakeMyTrip.com problems

drafts saved locally
public boolean hasDirectedCycle(int n, int[][] edges) {
    // Write your code here.
}
n4
edges[[0,1],[1,2],[2,0],[2,3]]
expectedtrue
checking account