Cycle Detection in Directed Graph in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection using DFS

What is the output of the following C++ code that detects a cycle in a directed graph using DFS?

DSA C++

/* Graph edges: 0->1, 1->2, 2->0, 2->3 */
#include <iostream>
#include <vector>
using namespace std;

bool dfs(int node, vector<vector<int>>& graph, vector<int>& visited) {
    visited[node] = 1; // visiting
    for (int nbr : graph[node]) {
        if (visited[nbr] == 0) {
            if (dfs(nbr, graph, visited)) return true;
        } else if (visited[nbr] == 1) {
            return true; // cycle found
        }
    }
    visited[node] = 2; // visited
    return false;
}

int main() {
    vector<vector<int>> graph(4);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(0);
    graph[2].push_back(3);

    vector<int> visited(4, 0);
    bool hasCycle = false;
    for (int i = 0; i < 4; i++) {
        if (visited[i] == 0) {
            if (dfs(i, graph, visited)) {
                hasCycle = true;
                break;
            }
        }
    }
    cout << (hasCycle ? "Cycle detected" : "No cycle") << endl;
    return 0;
}

A Compilation error

B No cycle

C Cycle detected

D Runtime error

💡 Hint

Think about the edges forming a loop: 0->1->2->0.

The graph has a cycle formed by nodes 0, 1, and 2. The DFS detects this cycle by revisiting a node currently in the recursion stack (visited[node] == 1).

❓ Predict Output

intermediate

Output of cycle detection using Kahn's Algorithm

What is the output of the following C++ code that detects a cycle in a directed graph using Kahn's Algorithm (topological sort)?

DSA C++

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

int main() {
    int n = 4;
    vector<vector<int>> graph(n);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(1); // back edge creating cycle

    vector<int> indegree(n, 0);
    for (int i = 0; i < n; i++) {
        for (int nbr : graph[i]) {
            indegree[nbr]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    int count = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        count++;
        for (int nbr : graph[node]) {
            indegree[nbr]--;
            if (indegree[nbr] == 0) q.push(nbr);
        }
    }

    cout << (count == n ? "No cycle" : "Cycle detected") << endl;
    return 0;
}

A Cycle detected

B No cycle

C Compilation error

D Runtime error

💡 Hint

Kahn's algorithm fails to process all nodes if a cycle exists.

The graph contains a cycle 1->2->3->1. Kahn's algorithm cannot process all nodes, so count < n, indicating a cycle.

🔧 Debug

advanced

Identify the bug in cycle detection DFS code

The following code is intended to detect a cycle in a directed graph using DFS. What is the bug causing incorrect results?

DSA C++

#include <vector>
using namespace std;

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

int main() {
    // graph initialization omitted
    return 0;
}

A visited vector should track three states, not just visited/unvisited

B dfs function should return void, not bool

C graph should be undirected for cycle detection

D visited vector should be of int type, not bool

💡 Hint

Think about how to detect back edges in DFS for directed graphs.

Using only a boolean visited vector cannot distinguish nodes currently in recursion stack from fully processed nodes, causing false cycle detection or misses.

🧠 Conceptual

advanced

Why does Kahn's Algorithm detect cycles in directed graphs?

Why does Kahn's Algorithm detect cycles in a directed graph?

A Because it uses DFS recursion stack to find back edges

B Because it counts the number of edges and compares with nodes

C Because it colors nodes with three states during traversal

D Because it fails to remove all nodes if a cycle exists, leaving nodes with non-zero indegree

💡 Hint

Think about what happens to indegree counts when a cycle is present.

Kahn's Algorithm removes nodes with zero indegree repeatedly. If a cycle exists, some nodes never reach zero indegree, so the algorithm cannot process all nodes.

🚀 Application

expert

Detect cycle and print one cycle path in directed graph

Given the following code snippet, what is the output when detecting a cycle and printing one cycle path in a directed graph?

DSA C++

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

bool dfs(int node, vector<vector<int>>& graph, vector<int>& visited, vector<int>& path, vector<int>& cycle) {
    visited[node] = 1; // visiting
    path.push_back(node);
    for (int nbr : graph[node]) {
        if (visited[nbr] == 0) {
            if (dfs(nbr, graph, visited, path, cycle)) return true;
        } else if (visited[nbr] == 1) {
            // cycle found, record cycle path
            auto it = find(path.begin(), path.end(), nbr);
            cycle.assign(it, path.end());
            return true;
        }
    }
    visited[node] = 2; // visited
    path.pop_back();
    return false;
}

int main() {
    vector<vector<int>> graph(5);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(1); // cycle 1->2->3->1
    graph[3].push_back(4);

    vector<int> visited(5, 0);
    vector<int> path, cycle;
    bool found = false;
    for (int i = 0; i < 5; i++) {
        if (visited[i] == 0) {
            if (dfs(i, graph, visited, path, cycle)) {
                found = true;
                break;
            }
        }
    }

    if (found) {
        for (int node : cycle) cout << node << " ";
    } else {
        cout << "No cycle";
    }
    cout << endl;
    return 0;
}

A 2 3 1

B 1 2 3

C 0 1 2 3

D No cycle

💡 Hint

The cycle path starts from the first node revisited in the recursion stack.

The cycle detected is 1->2->3->1. The code prints the cycle nodes starting from 1 to 3 in order.

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