Directed Graph Cycle

Time: O(V+E)

Space: O(V)

Intuition

A directed cycle exists iff DFS finds a back edge â€” an edge pointing to an ancestor in the current DFS stack. Use two states: "in-stack" (currently being explored) and "visited" (fully explored). A back edge leads to an "in-stack" node.

Algorithm

1visited[n]=false, inStack[n]=false.
2DFS(u): visited[u]=inStack[u]=true.
3For each neighbor v: if !visited: DFS(v). If cycle found, return true.
4Else if inStack[v]: return true (back edge â†’ cycle).
5inStack[u]=false. Return false.

Example Walkthrough

Input: Graph: 0â†’1â†’2â†’0 (cycle)

1.DFS(0): mark. DFS(1): mark. DFS(2): neighbor 0 is inStack â†’ cycle!

Output: true

Common Pitfalls

•For directed graphs, use inStack (recursion stack). For undirected graphs, just use visited + parent tracking.

Directed Graph Cycle.java

Java

// Approach: DFS with three states: unvisited, in-stack, visited. Cycle exists if DFS reaches an in-stack node.
// Time: O(V+E) Space: O(V)
import java.util.*;

class Solution {
    public boolean isCyclic(int V, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[V];

        for (int i = 0; i < V; i++)
            graph.add(new ArrayList<>());

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph.get(u).add(v);
            indegree[v]++;
        }

        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0)
                q.offer(i);
        }

        List<Integer> result = new ArrayList<>();

        while (!q.isEmpty()) {
            int node = q.poll();
            result.add(node);
            for (int adj : graph.get(node)) {
                indegree[adj]--;
                if (indegree[adj] == 0)
                    q.offer(adj);
            }
        }

        return result.size() != V;
    }
}

Was this solution helpful?