Cycle Detection in Undirected 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 an undirected graph using DFS?

DSA C

#include <stdio.h>
#include <stdbool.h>
#define V 4

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

int main() {
    int graph[V][V] = {
        {0, 1, 0, 0},
        {1, 0, 1, 1},
        {0, 1, 0, 1},
        {0, 1, 1, 0}
    };
    bool visited[V] = {false};
    bool hasCycle = false;
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, visited, graph)) {
                hasCycle = true;
                break;
            }
        }
    }
    if (hasCycle) {
        printf("Cycle detected\n");
    } else {
        printf("No cycle detected\n");
    }
    return 0;
}

A Cycle detected

B Compilation error

C No cycle detected

D Runtime error

💡 Hint

Trace the DFS calls and check if any back edge is found that is not the parent.

The graph has edges forming a cycle: nodes 1, 2, and 3 form a cycle. The DFS detects this cycle and prints "Cycle detected".

❓ Predict Output

intermediate

Output when graph has no cycle

What will be printed by this C code detecting cycles in an undirected graph without any cycles?

DSA C

#include <stdio.h>
#include <stdbool.h>
#define V 3

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

int main() {
    int graph[V][V] = {
        {0, 1, 0},
        {1, 0, 1},
        {0, 1, 0}
    };
    bool visited[V] = {false};
    bool hasCycle = false;
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, visited, graph)) {
                hasCycle = true;
                break;
            }
        }
    }
    if (hasCycle) {
        printf("Cycle detected\n");
    } else {
        printf("No cycle detected\n");
    }
    return 0;
}

A Cycle detected

B No cycle detected

C Segmentation fault

D Compilation error

💡 Hint

Check if any back edge exists that is not the parent.

The graph is a simple chain with no cycles. DFS will not find any back edge, so it prints "No cycle detected".

🔧 Debug

advanced

Identify the bug causing incorrect cycle detection

This code is intended to detect cycles in an undirected graph using DFS. What is the bug causing it to always print "No cycle detected" even when a cycle exists?

DSA C

#include <stdio.h>
#include <stdbool.h>
#define V 3

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

int main() {
    int graph[V][V] = {
        {0, 1, 1},
        {1, 0, 1},
        {1, 1, 0}
    };
    bool visited[V] = {false};
    bool hasCycle = false;
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, visited, graph)) {
                hasCycle = true;
                break;
            }
        }
    }
    if (hasCycle) {
        printf("Cycle detected\n");
    } else {
        printf("No cycle detected\n");
    }
    return 0;
}

A The recursive DFS call result is not returned, so true is never propagated up

B The visited array is not initialized properly

C The graph adjacency matrix is incorrect

D The parent parameter is not used in the DFS function

💡 Hint

Check if the recursive DFS calls return values are used properly.

The DFS function calls itself recursively but does not return the result of the recursive call. So even if a cycle is found deeper, it is not propagated back, causing the function to always return false.

🧠 Conceptual

advanced

Why is parent tracking necessary in cycle detection DFS?

In cycle detection for an undirected graph using DFS, why do we pass the parent node as a parameter and check if a visited neighbor is not the parent?

A To store the path of the DFS traversal

B To mark the parent node as visited

C To avoid counting the edge back to the parent as a cycle

D To prevent visiting the parent node again in BFS

💡 Hint

Think about why an edge to the immediate previous node should not be considered a cycle.

In an undirected graph, each edge is bidirectional. Without ignoring the parent, the DFS would always find the edge back to the parent as a cycle. So we exclude the parent to detect only real cycles.

🚀 Application

expert

Number of connected components with cycles

Given an undirected graph represented by adjacency matrix below, how many connected components contain at least one cycle?

DSA C

#define V 7
int graph[V][V] = {
    {0,1,0,0,0,0,0},
    {1,0,1,0,0,0,0},
    {0,1,0,0,0,0,0},
    {0,0,0,0,1,1,0},
    {0,0,0,1,0,1,0},
    {0,0,0,1,1,0,0},
    {0,0,0,0,0,0,0}
};

A 0

B 3

C 2

D 1

💡 Hint

Identify connected components and check each for cycles using DFS.

The graph has three connected components: nodes {0,1,2}, nodes {3,4,5}, and node {6} alone. The first component is a chain (no cycle), the second component forms a triangle (cycle), and the third is a single isolated node (no cycle). So only one component has a cycle.