Topics › Graphs › Problems on BFS/DFS

Cycle Detection in Directed Graph (DFS)

Hard TUF ID 2814 A2Z

Problem

You are given a directed graph with V vertices numbered 0 to V - 1, as an adjacency list where adj.get(u) holds every v with an edge u -> v. Return true if the graph contains a directed cycle: a path that follows edge directions and comes back to its starting vertex. A self-loop u -> u is a cycle. The graph may be disconnected.

Constraints: 1 ≤ V, E ≤ 10^5.

Example 1

1 -> 2 -> 3 -> 4 -> 5 -> 6         8 -> 9 -> 10
          |         ^              ^          |
          v         |              |__________|
          7 --------+
edges: 1->2, 2->3, 3->4, 3->7, 4->5, 5->6, 7->5, 8->9, 9->10, 10->8      (vertex 0 is isolated)
answer = true      // 8 -> 9 -> 10 -> 8

Example 2

the same graph without the edge 10 -> 8
answer = false

Example 2 is the important one. Vertex 5 is reachable along two routes, 3 -> 4 -> 5 and 3 -> 7 -> 5, so a DFS reaches 5 a second time. In an undirected graph that would mean a cycle. In a directed graph it does not: both routes flow forward and nothing leads back to 3. “I reached a visited vertex” is no longer enough; we need to know whether that vertex is still on the path we are currently walking.

Approach 1: Brute force, search from every vertex

Intuition. A cycle through vertex s exists exactly when some path starting at s leads back to s. So for each vertex run a fresh search over everything reachable from it, and stop if an edge points back to the start.

Algorithm.

For each vertex s:
Run an iterative DFS from s with its own seen array.
If any explored edge goes to s, return true.
If no start vertex succeeds, return false.

static boolean bruteForce(int V, List<List<Integer>> adj) {
    for (int s = 0; s < V; s++) {
        boolean[] seen = new boolean[V];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : adj.get(u)) {
                if (v == s) return true;             // walked back to the start
                if (!seen[v]) { seen[v] = true; stack.push(v); }
            }
        }
    }
    return false;
}

Complexity. Time O(V · (V + E)): one full search per vertex. Space O(V). With 10^5 vertices that is around 10^10 steps, because searches from different starts keep re-exploring the same vertices.

Approach 2: Optimal, DFS with a path-visited array

Intuition. Do one DFS over the whole graph, but track two facts per vertex:

vis[u]: u has been reached at some point;
pathVis[u]: u is on the current recursion path, meaning its DFS call has started and not yet returned.

When the DFS at u sees an edge u -> v:

v unvisited: recurse into it.
v visited and on the current path: v is an ancestor of u, so there is a path v -> ... -> u, and the edge u -> v closes it into a cycle. Return true.
v visited but no longer on the path: v is finished. Its call already explored everything reachable from v and found no cycle. Nothing new can come from it, so ignore it. This is exactly the vertex 5 situation in Example 2.

When the DFS at u returns, u leaves the path, so pathVis[u] is reset to false, but vis[u] stays true so u is never explored again.

Why does this always find a cycle when one exists? Let w be the first vertex of the cycle that the DFS reaches. At that moment every other vertex on the cycle is unvisited and reachable from w, so the DFS of w reaches all of them before w returns. In particular it reaches x, the vertex just before w on the cycle, while w is still on the path. The edge x -> w then hits pathVis[w] == true.

Algorithm.

For each unvisited vertex s, call dfsFindsCycle(s); return true if it does.
In dfsFindsCycle(u): set vis[u] and pathVis[u]. For each v: recurse if unvisited; return true if pathVis[v]. Before returning false, clear pathVis[u].

static boolean optimal(int V, List<List<Integer>> adj) {
    boolean[] vis = new boolean[V], pathVis = new boolean[V];
    for (int s = 0; s < V; s++) {
        if (!vis[s] && dfsFindsCycle(s, adj, vis, pathVis)) return true;
    }
    return false;
}

static boolean dfsFindsCycle(int u, List<List<Integer>> adj, boolean[] vis, boolean[] pathVis) {
    vis[u] = true;
    pathVis[u] = true;
    for (int v : adj.get(u)) {
        if (!vis[v]) {
            if (dfsFindsCycle(v, adj, vis, pathVis)) return true;
        } else if (pathVis[v]) {
            return true;                             // v is an ancestor of u: the edge u -> v closes a cycle
        }
    }
    pathVis[u] = false;                              // u leaves the current path
    return false;
}

Dry run on Example 1, following edges in the listed order:

step	event	path afterwards
1	0 has no edges and finishes; DFS 1 -> 2 -> 3 -> 4 -> 5 -> 6	1 2 3 4 5 6
2	6, 5, 4 finish	1 2 3
3	3 -> 7, then 7 -> 5: visited, not on path, ignore	1 2 3 7
4	7, 3, 2, 1 finish	empty
5	DFS 8 -> 9 -> 10	8 9 10
6	10 -> 8: 8 is on the path	cycle, return `true`

In Example 2, step 6 never happens and every call finishes, so the answer is false.

Complexity. Time O(V + E): each vertex starts one call, each edge is examined once. Space O(V) for the two arrays and the recursion stack.

Approach 3: Same DFS with one state array and an explicit stack

Intuition. The two boolean arrays describe three states, so a single int per vertex suffices: 0 unvisited, 1 on the current path, 2 finished. This is the classical white, grey and black colouring.

The bigger practical issue in Java is recursion depth. A chain of 10^5 vertices makes the recursive DFS 10^5 calls deep and overflows the default thread stack. An explicit stack holds the current path instead, and nextEdge[u] remembers which neighbour of u to try next, exactly like the loop variable that a suspended recursive call keeps. A vertex is popped and marked finished only when all its edges are exhausted, so “state 1” means precisely “on the stack”. The Java tests run this version on a chain of 200,000 vertices.

static boolean iterative(int V, List<List<Integer>> adj) {
    int[] state = new int[V];                        // 0 = unvisited, 1 = on current path, 2 = finished
    int[] nextEdge = new int[V];                     // index of the next neighbour to try
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < V; s++) {
        if (state[s] != 0) continue;
        stack.push(s);
        state[s] = 1;
        while (!stack.isEmpty()) {
            int u = stack.peek();
            if (nextEdge[u] < adj.get(u).size()) {
                int v = adj.get(u).get(nextEdge[u]++);
                if (state[v] == 1) return true;
                if (state[v] == 0) { state[v] = 1; stack.push(v); }
            } else {
                state[u] = 2;                        // all edges of u explored
                stack.pop();
            }
        }
    }
    return false;
}

Complexity. Time O(V + E), space O(V) for the arrays and the stack, all on the heap.

Edge cases and pitfalls

Using the undirected rule. “Visited and not my parent” reports a false cycle on Example 2. Directed graphs need the on-path check.
Forgetting to clear pathVis. If it is never reset, every finished vertex looks like an ancestor, and the second route into 5 in Example 2 is reported as a cycle.
Disconnected graphs. The cycle in Example 1 is in a component that a DFS from vertex 1 never touches; the outer loop over all vertices is required.
Self-loops. u -> u is found immediately because u is on the path when its own edge is examined.
Kahn’s algorithm is the BFS alternative: if a topological order cannot include every vertex, the graph has a cycle. It is covered in Detect a cycle in a directed graph.

Detect a cycle in a directed graph solves this with Kahn’s algorithm.
Detect a cycle in an undirected graph explains why the parent rule works there and fails here.
Topo Sort exists exactly for graphs without directed cycles.
Course Schedule I is this problem in disguise: courses are vertices, prerequisites are edges.
Find eventual safe states reuses the on-path information to classify every vertex.