Detect Cycle in Directed Graph

Problem Statement

You’re a graph sleuth inspecting a directed graph for cycles. Given vertices and edges, return true if a cycle exists. This medium-level DFS challenge is a dependency detective story—track recursion stack to catch loops!

Example

Input: V = 4, edges = [[0,1],[1,2],[2,3],[3,1]]

Graph:

0→1
  ↑ |
  | v
  3←2

Output: true (1→2→3→1)

Input: V = 3, edges = [[0,1],[1,2]]

Output: false (Acyclic)

Code

class Solution {
    public boolean hasCycle(int V, int[][] edges) {
        List> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) graph.get(edge[0]).add(edge[1]);
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];
        for (int i = 0; i < V; i++) {
            if (!visited[i] && dfs(graph, i, visited, recStack)) return true;
        }
        return false;
    }
    private boolean dfs(List> graph, int node, boolean[] visited, boolean[] recStack) {
        visited[node] = true;
        recStack[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor] && dfs(graph, neighbor, visited, recStack)) return true;
            else if (recStack[neighbor]) return true;
        }
        recStack[node] = false;
        return false;
    }
}
            

from collections import defaultdict
def has_cycle(V, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    visited = [False] * V
    rec_stack = [False] * V
    def dfs(node):
        visited[node] = True
        rec_stack[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor] and dfs(neighbor):
                return True
            elif rec_stack[neighbor]:
                return True
        rec_stack[node] = False
        return False
    for i in range(V):
        if not visited[i] and dfs(i):
            return True
    return False
            

function hasCycle(V, edges) {
    let graph = Array(V).fill().map(() => []);
    for (let [u, v] of edges) graph[u].push(v);
    let visited = new Array(V).fill(false);
    let recStack = new Array(V).fill(false);
    function dfs(node) {
        visited[node] = true;
        recStack[node] = true;
        for (let neighbor of graph[node]) {
            if (!visited[neighbor] && dfs(neighbor)) return true;
            else if (recStack[neighbor]) return true;
        }
        recStack[node] = false;
        return false;
    }
    for (let i = 0; i < V; i++) {
        if (!visited[i] && dfs(i)) return true;
    }
    return false;
}
            

Explanation

• DFS Insight: Cycle if a node in recursion stack is revisited—back edge detected.
• Flow: Build graph, DFS with recStack to track active path, check for loops.
• Example Walkthrough: [0,1],[1,2],[2,0] → 0→1→2→0 (in stack) → true.
• BFS Alt: Topological sort with in-degree—cycle if not all nodes processed.
• Key Detail: recStack differentiates between visited and currently exploring.

Note