Start practising

Directed Graph Cycle

Medium Graphs Cycle Detection Original on GeeksforGeeks

Directed Graph Cycle is a medium graphs problem solved with the cycle detection pattern. The best approach, kahn's algorithm (topological sort), runs in O(V + E) time and O(V) space. Below are 2 approaches in Java, from dfs with path tracking (three states) up.

Problem

Given a directed graph with V vertices and a list of edges, decide whether it contains a cycle.

Examples

Example 1

Input
V = 4, edges = [[0,1],[1,2],[2,3],[3,1]]
Output
true
Why
1 → 2 → 3 → 1.

Example 2

Input
V = 3, edges = [[0,1],[0,2],[1,2]]
Output
false
Why
2 is reached twice, but there is no directed loop.

Constraints

  • 1 <= V, E <= 10^5.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
DFS with path tracking (three states)O(V + E)O(V)
Kahn's algorithm (topological sort)O(V + E)O(V)

1DFS with path tracking (three states)

TimeO(V + E)
SpaceO(V)

State 0 = unvisited, 1 = on the current recursion path, 2 = finished. An edge into a state-1 node is a back edge, so there is a cycle.

  1. dfs(u): state[u] = 1.
  2. For each v: state 1 → true; state 0 and dfs(v) → true.
  3. state[u] = 2; return false.
Java
class Solution {
    public boolean isCyclic(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        int[] state = new int[V];
        for (int i = 0; i < V; i++) if (state[i] == 0 && dfs(i, adj, state)) return true;
        return false;
    }

    private boolean dfs(int u, List<List<Integer>> adj, int[] state) {
        state[u] = 1;
        for (int v : adj.get(u)) {
            if (state[v] == 1) return true;
            if (state[v] == 0 && dfs(v, adj, state)) return true;
        }
        state[u] = 2;
        return false;
    }
}

2Kahn's algorithm (topological sort)

TimeO(V + E)
SpaceO(V)

Repeatedly remove nodes with in-degree 0. If some nodes are never removed, they lie on a cycle.

  1. Compute in-degrees; queue all zeros.
  2. Pop, count, decrement neighbours' in-degrees, enqueue new zeros.
  3. Cycle if count < V.
Java
class Solution {
    public boolean isCyclic(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[V];
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < V; i++) if (indeg[i] == 0) q.add(i);
        int done = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            done++;
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
        }
        return done < V;
    }
}

Edge cases to test

  • Self-loop
  • A node reached twice without a cycle (the undirected visited check gives a false alarm here)

Hints

Hint 1

Reaching a node on the current DFS path means a cycle; reaching a node already finished does not. Track the path with a separate array or three colours.

FAQ

What is the best time complexity for Directed Graph Cycle?

Kahn's algorithm (topological sort) runs in O(V + E) time and O(V) extra space.

Which pattern does Directed Graph Cycle use?

It is a graphs problem that uses the cycle detection pattern. Other problems with the same pattern: Undirected Graph Cycle, Is Graph Bipartite?.

Is there a brute force solution for Directed Graph Cycle?

Yes. DFS with path tracking (three states) takes O(V + E) time and O(V) space. State 0 = unvisited, 1 = on the current recursion path, 2 = finished.

Which edge cases should I test for Directed Graph Cycle?

Self-loop; A node reached twice without a cycle (the undirected visited check gives a false alarm here).