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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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.
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?, Detect Cycles in 2D Grid.

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).