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.

How to spot this pattern

Direction changes everything: a revisited vertex is only a cycle if it's still on the current path. Three colours capture that — white unvisited, grey on the recursion stack, black finished. Seeing a grey vertex means you've looped back into your own path; black is a finished sibling branch and harmless.

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

▶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

Common pitfalls

Using a single visited flag

✗ Wrong

if seen[u]: return True

✓ Right

if color[u] == GREY: return True
if color[u] == WHITE and dfs(u): return True

In a DAG like a→b, a→c, b→c, vertex c is legitimately reached twice and a boolean flag calls that a cycle. Only a vertex still on the current path — grey — indicates a genuine back edge.

Never setting vertices black

✗ Wrong

def dfs(v):
    color[v] = GREY
    ...
    return False

✓ Right

    ...
    color[v] = BLACK
    return False

A vertex that stays grey after its branch finishes looks like it's still on the path, so a later unrelated branch reaching it reports a false cycle. Repainting on the way out is what marks the frame as popped.

Reusing the undirected parent trick

✗ Wrong

elif u != parent: return True

✓ Right

if color[u] == GREY: return True

Directed edges are one-way, so there's no mirrored edge to excuse and the parent test is meaningless — worse, a genuine 2-cycle a→b, b→a would be excused as the parent. Colour, not parentage, is the right signal here.

06

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.

07

Complexity

Time

O(V + E)

Space

O(V)

One colour array; each edge examined once.