15-Detect-Cycle-in-Directed-Graph.md

Detect Cycle in Directed Graph

Problem Link

Practice Problem

---

Pattern

• DFS
• Topological Sort

---

Approach

Use a recursion stack or color array to detect back edges in a directed graph.

---

Time Complexity

O(V + E)

Space Complexity

O(V)

---

Java Solution

import java.util.*;
class Solution {
    public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
        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 node, ArrayList<ArrayList<Integer>> adj, int[] state) {
        state[node] = 1;
        for (int next : adj.get(node)) {
            if (state[next] == 1) return true;
            if (state[next] == 0 && dfs(next, adj, state)) return true;
        }
        state[node] = 2;
        return false;
    }
}