Detect a cycle in a directed graph

Hard

Recursion stack, or a failed topological sort

Problem

Return whether a directed graph has a cycle.

In simple words

DFS with three colours; seeing a node still 'in progress' (grey) means you've found a back-edge cycle.

The idea

Either run DFS tracking which vertices are on the current path, or run Kahn's algorithm and check whether it managed to output every vertex. If some remain, they are locked in a cycle.

The trick

Kahn's leftover count is exactly the vertices inside cycles.
The undirected parent trick does not apply here.

←→stepspaceplay

indegrees[0,1,2,1]

1/6

Optimal

timeO(V+E)spaceO(V+E)

Cycle ⇒ impossible.

1q = every course whose indegree is 02while q not empty:3  c = q.pop(); processed += 14  for nb in adj[c]: indeg[nb] -= 1; if now 0, q.push(nb)5return processed == numCourses

Input

nodes: 4, 4 edges

Memory

indegrees: [0,1,2,1]
processed: —

Output

finish: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n=4, edges=[[0,1],[1,2],[2,3],[3,1]]
Output:: true
Explanation:: 3→1 closes a directed loop.

Example 2

Input:: n=3, edges=[[0,1],[1,2]]
Output:: false
Explanation:: A straight chain → no cycle.

Example 3

Input:: n=2, edges=[[0,1],[1,0]]
Output:: true
Explanation:: Mutual arrows form a cycle.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.