Cycle Detection in Undirected Graph in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection on a simple graph

What is the output of the following C# code that detects a cycle in an undirected graph?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    int V;
    List<int>[] adj;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w) {
        adj[v].Add(w);
        adj[w].Add(v);
    }

    private bool DFS(int v, bool[] visited, int parent) {
        visited[v] = true;
        foreach (int i in adj[v]) {
            if (!visited[i]) {
                if (DFS(i, visited, v))
                    return true;
            } else if (i != parent) {
                return true;
            }
        }
        return false;
    }

    public bool IsCyclic() {
        bool[] visited = new bool[V];
        for (int u = 0; u < V; u++) {
            if (!visited[u]) {
                if (DFS(u, visited, -1))
                    return true;
            }
        }
        return false;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(4);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.AddEdge(2, 3);
        g.AddEdge(3, 0);
        Console.WriteLine(g.IsCyclic());
    }
}

A Compilation error

B True

C Runtime exception

D False

💡 Hint

Think about whether the graph edges form a loop.

The graph has edges forming a cycle: 0-1-2-3-0. The DFS detects this cycle and returns true.

❓ Predict Output

intermediate

Cycle detection output on a tree structure

What will the output be when running this C# code that checks for cycles in an undirected graph structured as a tree?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    int V;
    List<int>[] adj;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w) {
        adj[v].Add(w);
        adj[w].Add(v);
    }

    private bool DFS(int v, bool[] visited, int parent) {
        visited[v] = true;
        foreach (int i in adj[v]) {
            if (!visited[i]) {
                if (DFS(i, visited, v))
                    return true;
            } else if (i != parent) {
                return true;
            }
        }
        return false;
    }

    public bool IsCyclic() {
        bool[] visited = new bool[V];
        for (int u = 0; u < V; u++) {
            if (!visited[u]) {
                if (DFS(u, visited, -1))
                    return true;
            }
        }
        return false;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(3);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        Console.WriteLine(g.IsCyclic());
    }
}

A Runtime exception

B True

C Compilation error

D False

💡 Hint

A tree has no cycles.

The graph is a tree with edges 0-1 and 1-2, so no cycles exist. The code returns false.

🔧 Debug

advanced

Identify the bug causing incorrect cycle detection

The following code is intended to detect cycles in an undirected graph. However, it incorrectly reports no cycle for a graph that has one. What is the bug?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    int V;
    List<int>[] adj;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w) {
        adj[v].Add(w);
        adj[w].Add(v);
    }

    private bool DFS(int v, bool[] visited, int parent) {
        visited[v] = true;
        foreach (int i in adj[v]) {
            if (!visited[i]) {
                if (DFS(i, visited, v))
                    return true;
            } else if (i == parent) {
                return true;
            }
        }
        return false;
    }

    public bool IsCyclic() {
        bool[] visited = new bool[V];
        for (int u = 0; u < V; u++) {
            if (!visited[u]) {
                if (DFS(u, visited, -1))
                    return true;
            }
        }
        return false;
    }
}

A The condition 'else if (i == parent)' should be 'else if (i != parent)'

B The adjacency list is not initialized properly

C The DFS does not mark nodes as visited

D The graph edges are not added bidirectionally

💡 Hint

Check the condition that detects a back edge indicating a cycle.

The code incorrectly returns true when the adjacent node is the parent, which is normal in undirected graphs. It should return true only if the adjacent node is visited and not the parent.

🧠 Conceptual

advanced

Understanding cycle detection logic in undirected graphs

In cycle detection for undirected graphs using DFS, why do we pass the parent node as a parameter during recursion?

A To avoid counting the edge to the parent as a cycle

B To keep track of the depth of recursion

C To mark the parent node as visited

D To store the path of nodes visited

💡 Hint

Think about why revisiting the immediate previous node is not a cycle.

In undirected graphs, the edge back to the parent is normal and should not be considered a cycle. Passing the parent helps ignore this edge.

🚀 Application

expert

Number of connected components with cycles

Given the following undirected graph edges, how many connected components contain at least one cycle? Edges: 0-1, 1-2, 2-0, 3-4, 4-5, 5-3, 6-7 Use the cycle detection logic to determine the count.

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    int V;
    List<int>[] adj;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w) {
        adj[v].Add(w);
        adj[w].Add(v);
    }

    private bool DFS(int v, bool[] visited, int parent) {
        visited[v] = true;
        foreach (int i in adj[v]) {
            if (!visited[i]) {
                if (DFS(i, visited, v))
                    return true;
            } else if (i != parent) {
                return true;
            }
        }
        return false;
    }

    public int CountComponentsWithCycle() {
        bool[] visited = new bool[V];
        int count = 0;
        for (int u = 0; u < V; u++) {
            if (!visited[u]) {
                if (DFS(u, visited, -1)) {
                    count++;
                }
            }
        }
        return count;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(8);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(3, 4);
        g.AddEdge(4, 5);
        g.AddEdge(5, 3);
        g.AddEdge(6, 7);
        Console.WriteLine(g.CountComponentsWithCycle());
    }
}

A 0

B 1

C 2

D 3

💡 Hint

Count connected groups and check which have cycles.

There are three connected components: {0,1,2}, {3,4,5}, and {6,7}. The first two have cycles, the last does not. So count is 2.

Practice

1. What is the main idea behind detecting a cycle in an undirected graph using DFS?

easy

A. If we visit a node that is already visited and is not the parent, a cycle exists.

B. If all nodes are visited exactly once, there is a cycle.

C. If the graph has more edges than nodes, it must have a cycle.

D. If the graph is disconnected, it contains a cycle.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and keeps track of the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If during DFS, a visited node is found that is not the parent of the current node, it means a cycle exists.

3. Final Answer:

   If we visit a node that is already visited and is not the parent, a cycle exists. -> Option A

4. Quick Check:

   Cycle detection in undirected graph = check visited node not parent [OK]

Hint: Check visited nodes excluding parent during DFS [OK]

Common Mistakes:

• Ignoring parent node in cycle check
• Assuming disconnected graph always has cycle
• Confusing cycle detection with edge count

2. Which of the following C# code snippets correctly initializes an adjacency list for an undirected graph with 3 nodes?

easy

A. var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>();

B. var graph = new List<int>[3]; graph = new List<int>();

C. List<int> graph = new List<int>[3];

D. var graph = new List(); graph.Add(new List<int>());

Solution

1. Step 1: Understand adjacency list initialization

   We need an array of lists, each list initialized separately to hold neighbors.

2. Step 2: Check code correctness

   var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>(); creates an array of List<int> and initializes each element with a new List<int>, which is correct.

3. Final Answer:

   var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>(); -> Option A

4. Quick Check:

   Initialize array of lists with loop [OK]

Hint: Initialize each list in array separately [OK]

Common Mistakes:

• Not initializing each list element
• Using wrong data types for adjacency list
• Assigning list directly to array variable

3. Consider the following C# code snippet for cycle detection in an undirected graph:

bool DFS(int node, int parent, List<int>[] graph, bool[] visited) {
    visited[node] = true;
    foreach(var neighbor in graph[node]) {
        if(!visited[neighbor]) {
            if(DFS(neighbor, node, graph, visited)) return true;
        } else if(neighbor != parent) {
            return true;
        }
    }
    return false;
}

// Graph edges: 0-1, 1-2, 2-0
// Call: DFS(0, -1, graph, visited)

What will be the output of this DFS call?

medium

A. Compilation error

B. false

C. StackOverflowException

D. true

Solution

1. Step 1: Analyze graph structure and DFS call

   The graph has edges 0-1, 1-2, and 2-0 forming a triangle cycle. DFS starts at node 0 with parent -1.

2. Step 2: Trace DFS for cycle detection

   DFS visits 0, then 1, then 2. When 2 checks neighbors, it finds 0 already visited and not parent, so returns true indicating cycle.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Triangle graph cycle detected = true [OK]

Hint: Cycle if visited neighbor not parent found [OK]

Common Mistakes:

• Ignoring parent check causing false cycle
• Assuming no cycle in triangle graph
• Confusing return values in recursion

4. The following C# code attempts to detect a cycle in an undirected graph but has a bug:

bool DFS(int node, int parent, List<int>[] graph, bool[] visited) {
    visited[node] = true;
    foreach(var neighbor in graph[node]) {
        if(!visited[neighbor]) {
            if(DFS(neighbor, node, graph, visited)) return true;
        } else {
            return true;
        }
    }
    return false;
}

What is the bug in this code?

medium

A. It never marks nodes as visited.

B. It returns true even if the visited neighbor is the parent node.

C. It does not traverse all neighbors.

D. It causes infinite recursion.

Solution

1. Step 1: Review cycle detection condition

   The code returns true if a neighbor is visited, but does not check if neighbor is parent.

2. Step 2: Identify why this causes incorrect cycle detection

   In undirected graphs, the parent node is always visited, so returning true here falsely detects a cycle.

3. Final Answer:

   It returns true even if the visited neighbor is the parent node. -> Option B

4. Quick Check:

   Must exclude parent node in cycle check [OK]

Hint: Exclude parent node when checking visited neighbors [OK]

Common Mistakes:

• Missing parent check in visited condition
• Assuming any visited neighbor means cycle
• Not marking nodes visited before recursion

5. You have an undirected graph represented as adjacency list:

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

Using DFS cycle detection, which node will first detect the cycle and why?

hard

A. Node 4, because it has only one neighbor.

B. Node 0, because it starts the DFS traversal.

C. Node 2, because it connects back to already visited node 0.

D. Node 1, because it has the smallest index among neighbors.

Solution

1. Step 1: Understand graph structure and DFS traversal

   Assuming neighbor lists are processed in listed order, DFS starts at node 0, visits 1 (first neighbor), then 3 (from 1), then 2 (from 3).

2. Step 2: Identify where cycle is detected

   Node 2 has neighbors 0 and 3; 0 is already visited and not parent (parent=3), so cycle is detected at node 2 first.

3. Final Answer:

   Node 2, because it connects back to already visited node 0. -> Option C

4. Quick Check:

   Cycle detected at node with visited neighbors not parent [OK]

Hint: Cycle detected where visited neighbors not parent found first [OK]

Common Mistakes:

• Assuming cycle detected at start node
• Ignoring multiple visited neighbors
• Confusing leaf nodes with cycle detection