Cycle Detection in Undirected Graph in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the adjacency list for the graph.

DSA C#

List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
    graph[i] = new [1]<int>();
}

Drag options to blanks, or click blank then click option'

AHashSet

BQueue

CDictionary

DList

Attempts:

3 left

💡 Hint

Common Mistakes

Using a Dictionary or Queue instead of a List for adjacency list initialization.

We use List<int> to store neighbors for each node in the adjacency list.

2fill in blank

medium

Complete the code to add an undirected edge between two nodes u and v.

DSA C#

graph[u].Add([1]);
graph[v].Add(u);

Drag options to blanks, or click blank then click option'

Au

Bgraph

Cv

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Adding the wrong node or adding the same node twice.

We add v to u's list and u to v's list to represent an undirected edge.

3fill in blank

hard

Fix the error in the DFS method signature for cycle detection.

DSA C#

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

Drag options to blanks, or click blank then click option'

Anode

Bparent

Cvisited

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Passing the parent parameter instead of the current node.

When calling DFS recursively, the current node becomes the parent for the neighbor.

4fill in blank

hard

Fill both blanks to complete the cycle detection loop over all nodes.

DSA C#

for (int i = 0; i < [1]; i++) {
    if (!visited[i]) {
        if (DFS(i, [2], visited, graph)) {
            return true;
        }
    }
}

Drag options to blanks, or click blank then click option'

An

B-1

C0

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as parent or looping incorrectly over nodes.

We loop from 0 to n-1 and start DFS with parent as -1 (no parent).

5fill in blank

hard

Fill all three blanks to complete the cycle detection method.

DSA C#

public bool HasCycle(int n, List<int>[] graph) {
    bool[] visited = new bool[[1]];
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (DFS(i, [2], visited, graph)) {
                return [3];
            }
        }
    }
    return false;
}

Drag options to blanks, or click blank then click option'

An

B-1

Ctrue

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Incorrect visited array size or wrong return value on cycle detection.

We create a visited array of size n, start DFS with parent -1, and return true if a cycle is found.

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