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

#include <stdio.h>
#include <stdbool.h>

#define V 4

bool dfs(int v, bool graph[V][V], bool visited[V], bool recStack[V]) {
    if(!visited[v]) {
        visited[v] = true;
        recStack[v] = true;

        for(int i = 0; i < V; i++) {
            if(graph[v][i]) {
                if(!visited[i] && dfs(i, graph, visited, recStack))
                    return true;
                else if(recStack[i])
                    return true;
            }
        }
    }
    recStack[v] = false;
    return false;
}

bool isCyclic(bool graph[V][V]) {
    bool visited[V] = {false};
    bool recStack[V] = {false};

    for(int i = 0; i < V; i++) {
        if(dfs(i, graph, visited, recStack))
            return true;
    }
    return false;
}

int main() {
    bool graph[V][V] = {
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1},
        {1, 0, 0, 0}
    };

    if(isCyclic(graph))
        printf("Cycle detected\n");
    else
        printf("No cycle detected\n");

    return 0;
}

A Cycle detected

B No cycle detected

C Compilation error

D Runtime error

💡 Hint

Trace the DFS calls and check if any node is revisited in the current recursion stack.

The graph has edges 0->1, 1->2, 2->3, and 3->0 forming a cycle. The DFS detects this cycle by checking the recursion stack.

🧠 Conceptual

intermediate

Understanding recursion stack in cycle detection

In cycle detection for a directed graph using DFS, what is the purpose of the recursion stack (recStack) array?

A To keep track of all visited nodes globally

B To keep track of nodes currently in the recursion path to detect back edges

C To store the order of nodes visited for topological sort

D To count the number of edges from each node

💡 Hint

Think about how a cycle is detected during DFS traversal.

The recursion stack marks nodes currently being explored. If a node is revisited while still in the recursion stack, it means a cycle exists.

🔧 Debug

advanced

Identify the error in cycle detection code

What error will occur when running this modified cycle detection code?

DSA C

#include <stdio.h>
#include <stdbool.h>

#define V 3

bool dfs(int v, bool graph[V][V], bool visited[V], bool recStack[V]) {
    visited[v] = true;
    recStack[v] = true;

    for(int i = 0; i < V; i++) {
        if(graph[v][i]) {
            if(!visited[i] && dfs(i, graph, visited, recStack))
                return true;
            else if(recStack[i])
                return true;
        }
    }
    recStack[v] = false;
    return false;
}

bool isCyclic(bool graph[V][V]) {
    bool visited[V] = {false};
    bool recStack[V] = {false};

    for(int i = 0; i < V; i++) {
        if(dfs(i, graph, visited, recStack))
            return true;
    }
    return false;
}

int main() {
    bool graph[V][V] = {
        {0, 1, 0},
        {0, 0, 1},
        {0, 0, 0}
    };

    if(isCyclic(graph))
        printf("Cycle detected\n");
    else
        printf("No cycle detected\n");

    return 0;
}

A No error, prints 'Cycle detected'

B Stack overflow due to infinite recursion

C Array index out of bounds error

D Compilation error due to missing header

💡 Hint

Check the loop bounds in isCyclic function.

The loop in isCyclic runs from 0 to V inclusive, causing an out-of-bounds access when i == V.

🚀 Application

advanced

Detect cycle in a graph with multiple disconnected components

Given a directed graph with 5 nodes and edges: 0->1, 1->2, 3->4, 4->3, which statement about cycle detection is true?

A The graph has a cycle only in the component containing nodes 3 and 4

B The graph has no cycles because components are disconnected

C The graph has a cycle in the component containing nodes 0,1,2

D The graph has cycles in both components

💡 Hint

Check edges in each disconnected component separately.

Nodes 3 and 4 form a cycle (3->4 and 4->3). The other component 0->1->2 has no cycle.

🧠 Conceptual

expert

Why can't BFS alone detect cycles in directed graphs reliably?

Why is BFS not typically used alone to detect cycles in directed graphs?

A BFS can only detect cycles in undirected graphs

B BFS always detects cycles incorrectly in directed graphs

C BFS requires more memory than DFS for cycle detection

D BFS cannot detect back edges which indicate cycles in directed graphs

💡 Hint

Think about how cycle detection relies on back edges and recursion stack.

Cycle detection in directed graphs depends on detecting back edges during DFS. BFS does not track recursion paths and thus cannot reliably detect cycles alone.

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 that starts and ends at the same node following the direction of edges.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists 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 = path starting and ending at same node [OK]

Hint: Cycle means path loops back to start following edges [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Thinking cycle ignores edge directions
• Mixing cycle detection with counting nodes

2. Which of the following is the correct way to declare a visited array for cycle detection in C for a graph with n nodes?

easy

A. int visited = new int[n];

B. int visited[n] = {0};

C. int visited[] = {0};

D. int visited[n];

Solution

1. Step 1: Understand array declaration in C

   In C, to declare an array of size n, use int visited[n]; but it is uninitialized.

2. Step 2: Initialize array to zero

   To initialize all elements to zero, use int visited[n] = {0}; which sets all to zero.

3. Final Answer:

   int visited[n] = {0}; -> Option B

4. Quick Check:

   Array declaration with zero init = int visited[n] = {0}; [OK]

Hint: Use int arr[n] = {0} to initialize all zeros in C [OK]

Common Mistakes:

• Using 'new' keyword which is C++ not C
• Declaring array without size
• Incorrect initialization syntax

3. Consider the following C code snippet for cycle detection in a directed graph using DFS. What will be the output?

void dfs(int node, int visited[], int recStack[], int graph[][3]) {
    visited[node] = 1;
    recStack[node] = 1;
    for (int i = 0; i < 3; i++) {
        int adj = graph[node][i];
        if (adj == -1) continue;
        if (!visited[adj]) dfs(adj, visited, recStack, graph);
        else if (recStack[adj]) printf("Cycle detected\n");
    }
    recStack[node] = 0;
}

int main() {
    int graph[3][3] = {{1, -1, -1}, {2, -1, -1}, {0, -1, -1}};
    int visited[3] = {0}, recStack[3] = {0};
    dfs(0, visited, recStack, graph);
    return 0;
}

medium

A. No output

B. Infinite loop

C. Segmentation fault

D. Cycle detected

Solution

1. Step 1: Analyze graph edges

   Graph edges: 0->1, 1->2, 2->0 form a cycle.

2. Step 2: Trace DFS calls and cycle detection

   DFS visits 0, then 1, then 2. When 2 tries to visit 0 again which is in recursion stack, it prints "Cycle detected".

3. Final Answer:

   Cycle detected -> Option D

4. Quick Check:

   Cycle in graph triggers print "Cycle detected" [OK]

Hint: Cycle prints when node revisited in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming no output means no cycle
• Confusing visited and recursion stack arrays

4. The following code attempts to detect a cycle in a directed graph but does not work correctly. What is the main error?

void dfs(int node, int visited[], int graph[][3]) {
    visited[node] = 1;
    for (int i = 0; i < 3; i++) {
        int adj = graph[node][i];
        if (adj == -1) continue;
        if (!visited[adj]) dfs(adj, visited, graph);
        else printf("Cycle detected\n");
    }
}

int main() {
    int graph[3][3] = {{1, -1, -1}, {2, -1, -1}, {0, -1, -1}};
    int visited[3] = {0};
    dfs(0, visited, graph);
    return 0;
}

medium

A. Graph adjacency matrix is incorrect

B. Visited array is not initialized

C. Missing recursion stack to track nodes in current path

D. DFS function missing return type

Solution

1. Step 1: Understand cycle detection logic

   Cycle detection in directed graph needs to track nodes in current recursion path using a recursion stack.

2. Step 2: Identify missing recursion stack

   This code only uses visited array, so it cannot distinguish back edges causing cycles from cross edges.

3. Final Answer:

   Missing recursion stack to track nodes in current path -> Option C

4. Quick Check:

   Recursion stack needed for correct cycle detection [OK]

Hint: Use recursion stack to detect back edges in DFS [OK]

Common Mistakes:

• Assuming visited array alone detects cycles
• Ignoring need to track current DFS path
• Confusing undirected and directed cycle detection

5. You have a directed graph represented as adjacency lists:

0: [1]
1: [2]
2: [3, 4]
3: [1]
4: []

Which nodes are part of a cycle detected by DFS cycle detection algorithm?

hard

A. Nodes 1, 2, 3

B. Nodes 0, 1, 4

C. Nodes 0, 2, 4

D. Nodes 3, 4

Solution

1. Step 1: Trace the graph edges

   Edges: 0->1, 1->2, 2->3 and 2->4, 3->1.

2. Step 2: Identify cycle nodes

   Cycle is 1->2->3->1. Nodes 1, 2, 3 form the cycle.

3. Final Answer:

   Nodes 1, 2, 3 -> Option A

4. Quick Check:

   Cycle nodes = 1, 2, 3 [OK]

Hint: Follow edges to find loops including nodes [OK]

Common Mistakes:

• Including nodes not in cycle like 0 or 4
• Missing node 3 in cycle
• Confusing cycle with path