Back to ChallengesDetect Cycle in a Directed GraphMedium 25 min

Detect Cycle in a Directed Graph

Given a directed graph with **n** vertices and a list of directed edges, determine whether the graph contains a **cycle**.

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

Output: true

0→1→2→0 forms a directed cycle.

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

Output: false

A simple directed path.

Time

O(V + E)

Space

O(V)

color/state array of size 3 (white/gray/black) plus recursion stack.

#1 — Directed cycle

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

Expected: true

#2 — Directed path

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

Expected: false

#3 — Cycle not including start node

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

Expected: true

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.

Output

Click "Run Code" to see output here...