191. Detect a Directed Cycle with Three States

Why this mechanism works

A single visited flag cannot distinguish a completed branch from the current recursive ancestry. Use three states: unseen, active and finished. An edge to an active vertex closes a route back to an ancestor. An edge to a finished vertex merely reuses previously explored graph structure.

State and boundaries

state 0 means unvisited, 1 means on the active DFS call path, and 2 means all outgoing edges have been completely checked.

Protocol

1. Start DFS at each unseen vertex.
2. Mark the current vertex active.
3. Reject acyclicity on an edge to an active vertex.
4. Recursively inspect unseen neighbors.
5. Mark finished only after all outgoing edges return without a cycle.

Visualization

0(active) -> 1(active) -> 2(active) -> 0
edge to active ancestor: cycle
edge to a finished node: already-checked branch

Python implementation

def directed_cycle(adj):
    state = [0] * len(adj)
    def visit(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1:
                return True
            if state[v] == 0 and visit(v):
                return True
        state[u] = 2
        return False
    return any(state[u] == 0 and visit(u) for u in range(len(adj)))

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 directed_cycle: state = [0] * len(adj)
adj=[[1], [2], [0]]; state=[0, 0, 0]

L4 visit: state[u] = 1
u=0; adj=[[1], [2], [0]]; state=[1, 0, 0]

L5 visit: for v in adj[u]:
u=0; adj=[[1], [2], [0]]; state=[1, 0, 0]; v=1

L4 visit: state[u] = 1
u=1; adj=[[1], [2], [0]]; state=[1, 1, 0]

L5 visit: for v in adj[u]:
u=1; adj=[[1], [2], [0]]; state=[1, 1, 0]; v=2

L4 visit: state[u] = 1
u=2; adj=[[1], [2], [0]]; state=[1, 1, 1]

L5 visit: for v in adj[u]:
u=2; adj=[[1], [2], [0]]; state=[1, 1, 1]; v=0

L8 visit: if state[v] == 0 and visit(v):
u=1; adj=[[1], [2], [0]]; state=[1, 1, 1]; v=2

L8 visit: if state[v] == 0 and visit(v):
u=0; adj=[[1], [2], [0]]; state=[1, 1, 1]; v=1

L12 <genexpr>: return any(state[u] == 0 and visit(u) for u in range(len(adj)))
.0=range_iterator; u=0; state=[1, 1, 1]

L12 directed_cycle: return any(state[u] == 0 and visit(u) for u in range(len(adj)))
adj=[[1], [2], [0]]; state=[1, 1, 1]

L2 directed_cycle: state = [0] * len(adj)
adj=[[1, 2], [2], []]; state=[0, 0, 0]

L4 visit: state[u] = 1
u=0; adj=[[1, 2], [2], []]; state=[1, 0, 0]

L5 visit: for v in adj[u]:
u=0; adj=[[1, 2], [2], []]; state=[1, 0, 0]; v=1

L4 visit: state[u] = 1
u=1; adj=[[1, 2], [2], []]; state=[1, 1, 0]

L5 visit: for v in adj[u]:
u=1; adj=[[1, 2], [2], []]; state=[1, 1, 0]; v=2

L4 visit: state[u] = 1
u=2; adj=[[1, 2], [2], []]; state=[1, 1, 1]

L10 visit: state[u] = 2
u=2; adj=[[1, 2], [2], []]; state=[1, 1, 2]

L8 visit: if state[v] == 0 and visit(v):
u=1; adj=[[1, 2], [2], []]; state=[1, 1, 2]; v=2

... 5 intermediate state changes omitted ...

L12 <genexpr>: return any(state[u] == 0 and visit(u) for u in range(len(adj)))
.0=range_iterator; u=1; state=[2, 2, 2]

L12 <genexpr>: return any(state[u] == 0 and visit(u) for u in range(len(adj)))
.0=range_iterator; u=2; state=[2, 2, 2]

L12 <genexpr>: return any(state[u] == 0 and visit(u) for u in range(len(adj)))
.0=range_iterator; u=2; state=[2, 2, 2]

L12 directed_cycle: return any(state[u] == 0 and visit(u) for u in range(len(adj)))
adj=[[1, 2], [2], []]; state=[2, 2, 2]

Why the solution is correct

An edge to an active ancestor combines with the DFS tree path to form a directed cycle. If a cycle exists, the first DFS exploration entering its unfinished vertices eventually encounters such a back edge. Finished vertices have already had every descendant edge checked, so cross edges to them are harmless.

Time and space

O(V+E) time and O(V) state plus recursion space. Deep graphs may require an iterative implementation.

Common mistakes

Marking a vertex finished before exploring its neighbors hides back edges. Treating every edge to any visited vertex as a cycle rejects DAGs with shared descendants.

Reasoning card

Transfer exercise

Implement the same three-state protocol with explicit frames storing each node's next neighbor index.