Cycle Detection in Directed Graph in DSA C++

Mental Model

We want to find if there is a path that starts and ends at the same node following the direction of edges.

Analogy: Imagine a one-way street map where you want to check if you can start driving from a place and come back to it by following the one-way roads without reversing.

Graph nodes with arrows showing direction:
1 -> 2 -> 3
↑         ↓
└─────────

Dry Run Walkthrough

Input: Graph with edges: 1->2, 2->3, 3->1 (cycle exists)

Goal: Detect if the graph contains a cycle following the direction of edges

Step 1: Start DFS from node 1, mark node 1 as visiting

Visiting: [1], Visited: []

Why: We begin exploring from node 1 to find cycles

Step 2: Move to node 2 from node 1, mark node 2 as visiting

Visiting: [1, 2], Visited: []

Why: Continue following edges to explore deeper

Step 3: Move to node 3 from node 2, mark node 3 as visiting

Visiting: [1, 2, 3], Visited: []

Why: Keep exploring to detect cycle

Step 4: From node 3, try to move to node 1 which is already visiting

Visiting: [1, 2, 3], Visited: []

Why: Finding a node in visiting state means a cycle is detected

Result:

Cycle detected because node 1 is revisited while still in visiting state

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;

    Graph(int V) {
        this->V = V;
        adj.resize(V + 1);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    bool dfs(int node, vector<int>& visited, vector<int>& recStack) {
        visited[node] = 1; // mark node as visited
        recStack[node] = 1; // mark node in recursion stack

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, visited, recStack))
                    return true; // cycle found in deeper call
            } else if (recStack[neighbor]) {
                return true; // cycle found due to back edge
            }
        }

        recStack[node] = 0; // remove node from recursion stack
        return false; // no cycle found from this node
    }

    bool isCyclic() {
        vector<int> visited(V + 1, 0);
        vector<int> recStack(V + 1, 0);

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

int main() {
    Graph g(3);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    if (g.isCyclic())
        cout << "Cycle detected\n";
    else
        cout << "No cycle detected\n";

    return 0;
}

visited[node] = 1; // mark node as visited recStack[node] = 1; // mark node in recursion stack

Mark current node as visited and add to recursion stack to track current path

for (int neighbor : adj[node]) {

Traverse all neighbors of current node

if (!visited[neighbor]) { if (dfs(neighbor, visited, recStack)) return true; // cycle found in deeper call }

If neighbor not visited, recursively visit it and check for cycle

else if (recStack[neighbor]) { return true; // cycle found due to back edge }

If neighbor is in recursion stack, cycle detected due to back edge

recStack[node] = 0; // remove node from recursion stack

Remove node from recursion stack after exploring all neighbors

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

Check all nodes to cover disconnected components

Output

Cycle detected

Complexity Analysis

Time: O(V + E) because each node and edge is visited once during DFS

Space: O(V) for recursion stack and visited arrays

vs Alternative: Compared to using cycle detection with coloring or topological sort, DFS recursion stack method is straightforward and efficient

Edge Cases

Empty graph (no nodes)

No cycle detected as there are no nodes or edges

DSA C++

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

Graph with no edges

No cycle detected because no edges exist to form a cycle

DSA C++

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

Graph with self-loop (node points to itself)

Cycle detected because node revisits itself in recursion stack

DSA C++

else if (recStack[neighbor]) { return true; }

When to Use This Pattern

When you see a problem asking if a directed graph has a cycle, use DFS with recursion stack to detect back edges indicating cycles.

Common Mistakes

Mistake: Checking only visited array without recursion stack leads to false negatives for cycles.
Fix: Use a separate recursion stack array to track nodes in the current DFS path.

Summary

Detects if a directed graph contains a cycle by tracking nodes in the current path.

Use when you need to know if a directed graph has cycles to avoid infinite loops or invalid states.

The key insight is that revisiting a node currently in the recursion stack means a cycle exists.

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. Whether there is a path that starts and ends at the same node following edge directions

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. The maximum degree of any node

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path where you can start from a node and follow edges in their direction to come back to the same node.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists anywhere in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following edge directions -> Option A

4. Quick Check:

   Cycle detection = find directed loops [OK]

Hint: Cycle means path back to start following edge directions [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Thinking cycle ignores edge directions
• Mixing cycle with node count

2. Which of the following is the correct way to declare a graph adjacency list in C++ for cycle detection?

easy

A. vector graph(100);

B. int graph[100][100];

C. map graph;

D. vector<int> graph[100];

Solution

1. Step 1: Understand adjacency list declaration

   For cycle detection, adjacency list is often a vector of vectors to store edges from each node.

2. Step 2: Check each option

   A: vector graph(100); - standard and flexible vector of vectors for adjacency list. B: adjacency matrix, not list. C: map, valid but less common and heavier for sequential nodes. D: array of vectors, works but fixed size and less modern than vector of vectors.

3. Final Answer:

   vector graph(100); -> Option A

4. Quick Check:

   Use vector of vectors for adjacency list [OK]

Hint: Use vector for flexible adjacency list [OK]

Common Mistakes:

• Using adjacency matrix instead of list
• Confusing map with vector
• Using raw arrays limiting flexibility

3. What will be the output of the following code snippet detecting cycle in a directed graph?

bool dfs(int node, vector& graph, vector<int>& visited, vector<int>& recStack) {
    visited[node] = 1;
    recStack[node] = 1;
    for (int adj : graph[node]) {
        if (!visited[adj] && dfs(adj, graph, visited, recStack))
            return true;
        else if (recStack[adj])
            return true;
    }
    recStack[node] = 0;
    return false;
}

int main() {
    vector graph(3);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(0);
    vector<int> visited(3, 0), recStack(3, 0);
    cout << (dfs(0, graph, visited, recStack) ? "Cycle Found" : "No Cycle") << endl;
    return 0;
}

medium

A. Compilation Error

B. Cycle Found

C. No Cycle

D. Runtime Error

Solution

1. Step 1: Analyze graph edges

   Edges: 0->1, 1->2, 2->0 form a cycle (0->1->2->0).

2. Step 2: Understand DFS cycle detection

   DFS uses recursion stack to detect back edges indicating cycle. Here, cycle exists, so dfs returns true.

3. Final Answer:

   Cycle Found -> Option B

4. Quick Check:

   Cycle in 0->1->2->0 detected [OK]

Hint: Check recursion stack for back edges to find cycle [OK]

Common Mistakes:

• Ignoring recursion stack usage
• Assuming no cycle in simple loops
• Confusing visited and recursion stack arrays

4. Find the bug in this cycle detection code snippet for a directed graph:

bool dfs(int node, vector& graph, vector<bool>& visited, vector<bool>& recStack) {
    visited[node] = true;
    for (int adj : graph[node]) {
        if (!visited[adj] && dfs(adj, graph, visited, recStack))
            return true;
        else if (recStack[adj])
            return true;
    }
    recStack[node] = false;
    return false;
}

medium

A. Graph should be vector<int> not vector

B. visited array should be int, not bool

C. Missing return statement in else block

D. recStack[node] is never set to true at start

Solution

1. Step 1: Check usage of recStack

   recStack marks nodes in current recursion path. It must be set true when node is entered.

2. Step 2: Identify missing recStack[node] = true

   Code sets recStack[node] = false at end but never sets it true at start, so cycle detection fails.

3. Final Answer:

   recStack[node] is never set to true at start -> Option D

4. Quick Check:

   Set recStack true on node entry [OK]

Hint: Always mark recStack true when entering node [OK]

Common Mistakes:

• Forgetting to set recStack true at start
• Confusing visited and recStack roles
• Wrong data types for visited array

5. Given a directed graph with nodes 0 to 4 and edges: 0->1, 1->2, 2->3, 3->1, 3->4, which nodes are part of a cycle?

hard

A. [0, 1, 2, 3]

B. [2, 3, 4]

C. [1, 2, 3]

D. [0, 4]

Solution

1. Step 1: Analyze edges for cycles

   Edges 1->2, 2->3, 3->1 form a cycle involving nodes 1, 2, 3.

2. Step 2: Identify nodes outside cycle

   Node 0 points to 1 but is not in cycle. Node 4 is only reached from 3 and has no outgoing edges back.

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   Cycle nodes = 1, 2, 3 [OK]

Hint: Cycle nodes form closed loop edges [OK]

Common Mistakes:

• Including nodes only pointing into cycle
• Including nodes with no back edges
• Confusing cycle membership with reachability