GeeksforGeeks Medium

Detect Cycle in Directed Graph (DFS)

Does a directed graph contain a cycle? Use DFS with three colours.

graphdfscyclecoloring

02

Intuition

💡

The undirected parent trick breaks here: reaching an already-visited vertex is fine if that vertex is completely finished — it just means two paths converge. What matters is whether the target is still on the current recursion stack. Three colours capture that: white (untouched), grey (on the stack), black (finished). An edge into grey is a cycle.

03

Approach

1

Why two states are not enough

With only visited/unvisited, the DAG 0→1, 0→2, 1→2 falsely reports a cycle when 0→2 finds 2 already visited. The fix is distinguishing 'finished' from 'in progress'.

2

Grey means on the stack

Colour a vertex grey on entry and black on exit. An edge into a grey vertex points back into the path currently being explored — a genuine cycle.

3

Black edges are safe

An edge into a black vertex is a shortcut into an already-completed subtree; it cannot close a loop, so it is ignored.

04

Solution & live demo

python

▶1WHITE, GREY, BLACK = 0, 1, 2
▶2 
▶3def has_cycle_directed_dfs(n, adj):
▶4    color = [WHITE] * n
▶5    def dfs(v):
▶6        color[v] = GREY           # on the recursion stack
▶7        for u in adj[v]:
▶8            if color[u] == GREY:  # points back into the path
▶9                return True
▶10            if color[u] == WHITE and dfs(u):
▶11                return True
▶12            # BLACK -> finished, harmless
▶13        color[v] = BLACK          # off the stack
▶14        return False
▶15    for s in range(n):            # every component
▶16        if color[s] == WHITE and dfs(s):
▶17            return True
▶18    return False

05

Edge cases

DAG with converging paths

The shared vertex is black by then, so no false positive.

Self-loop v→v

v is grey while its own edges are scanned — reported immediately.

Disconnected graph

Outer loop starts a DFS in each component.

06

Complexity

Time

O(V + E)

Space

O(V)

One colour array; each edge examined once.