Skip to main content

Cycle Detection in Directed Graph

Problem Statement:​

Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.The graph is represented as a 2D vector edges[][], where each entry edges[i] = [u, v] denotes an edge from verticex u to v.

Examples:

Input:V = 4, edges[][] = [[0, 1], [0, 2], [1, 2], [2, 0], [2, 3]]
Output: true
Explanation: The diagram clearly shows a cycle 0 → 2 → 0

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

Output: false
Explanation: no cycle in the graph

  • Example:

✅ Solution: DFS with Recursion Stack — Detect Cycle in Directed Graph​

class Solution {
  public:
    bool dfs(int node, vector<bool> &visited, vector<bool> &recStack, vector<vector<int>> &adj) {
        visited[node] = true;
        recStack[node] = true;

        for (auto neighbor : adj[node]) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, visited, recStack, adj)) return true;
            } else if (recStack[neighbor]) {
                return true;  // Cycle detected
            }
        }

        recStack[node] = false;
        return false;
    }

    bool isCyclic(int V, vector<vector<int>> &edges) {
        vector<bool> visited(V, false);
        vector<bool> recStack(V, false);
        vector<vector<int>> adj(V);

        for (auto &edge : edges) {
            adj[edge[0]].push_back(edge[1]);
        }

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, visited, recStack, adj)) return true;
            }
        }

        return false;
    }
};

📝 How It Works​

  • Objective: Detect if there is a cycle in a directed graph.

  • Technique:

    Use DFS with a recursion stack (recStack array):

    • visited[] tracks visited nodes overall.
    • recStack[] tracks nodes in the current DFS call path.

  • Step-by-Step:

    1. Convert edge list to adjacency list.
    2. For each unvisited node:
      • Run DFS.
      • If we visit a node already in the current path (recStack), it means there’s a cycle.
    3. If no cycles found after checking all nodes, return false.

  • Why This Works:

    • Recursion stack ensures we only detect back edges specific to directed graphs.

🧩 Key Formula / Recurrence​

DFS recurrence:

if (!visited[neighbor]) {
    dfs(neighbor, visited, recStack, adj)
} else if (recStack[neighbor]) {
    return true;  // Cycle found
}

⏱️ Time & Space Complexity​

MetricValue
Time ComplexityO(V + E)
Space ComplexityO(V + E)
  • V = number of vertices
  • E = number of edges
  • Adjacency list + recursion stack + visited arrays.

⚠️ Edge Cases​

  • No edges → No cycle.
  • Multiple components → Must check all.
  • Self-loop → Immediate cycle.

💡 Other Approaches​

ApproachTime ComplexityNotes
Kahn’s Algorithm (BFS)O(V + E)Topological Sort check. Works for DAG cycle detection.

🔁 Related Problems​

  • LeetCode 207: Course Schedule (Exact Problem)
  • LeetCode 210: Course Schedule II
  • LeetCode 2360: Longest Cycle in a Graph

🛠️ Other Notes​

  • ✅ Real-World Analogy:

    Detecting circular dependencies in build systems or package management (e.g., npm/yarn dependency graphs).

  • ✅ Works for disconnected graphs since we run DFS from all unvisited nodes.

  • ✅ Self-loop and back-edge handling is automatic with recStack.

💬

Discussion & Doubts