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

Practice - 5 Tasks

1fill in blank

easy

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

DSA C#

List<int>[] graph = new List<int>[[1]];

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

An

Bcount

Cedges

Dnodes

Attempts:

3 left

💡 Hint

Common Mistakes

Using the number of edges instead of nodes.

Using an undefined variable.

The adjacency list size should be equal to the number of nodes, which is stored in variable n.

2fill in blank

medium

Complete the code to add an edge from node u to node v in the adjacency list.

DSA C#

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

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

AAdd

Badd

Cappend

DInsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using lowercase 'add' which is invalid in C#.

Using 'append' which is not a List method in C#.

In C#, the method to add an element to a List is Add with capital A.

3fill in blank

hard

Fix the error in the DFS method to mark the current node as visited.

DSA C#

visited[node] = [1];

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

Afalse

Btrue

Cnull

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited as false instead of true.

Using integer 1 instead of boolean true.

When visiting a node, mark it as true in the visited array.

4fill in blank

hard

Fill both blanks to check if a neighbor node is in the recursion stack.

DSA C#

if (recStack[[1]])
{
    return [2];
}

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

Aneighbor

Btrue

Cnode

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Checking the wrong node variable.

Returning false instead of true on cycle detection.

We check if the neighbor is in the recursion stack and return true if a cycle is detected.

5fill in blank

hard

Fill all three blanks to remove the current node from recursion stack and return no cycle found.

DSA C#

recStack[[1]] = [2];
return [3];

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

Anode

Bfalse

Ctrue

Dneighbor

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true instead of false when no cycle is found.

Not removing the node from recursion stack.

After exploring all neighbors, remove the node from recursion stack and return false indicating no cycle found in this path.

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 vertex following edge directions

B. The shortest path between two vertices

C. The total number of vertices in the graph

D. The maximum degree of any vertex

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same vertex 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 vertex following edge directions -> Option A

4. Quick Check:

   Cycle detection = finding directed cycles [OK]

Hint: Cycle means path loops back following edge directions [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Ignoring edge directions
• Thinking cycle means any repeated vertex

2. Which C# data structure is commonly used to keep track of nodes currently in the recursion stack during DFS for cycle detection?

easy

A. Queue

B. Stack or boolean array to mark recursion stack

C. Dictionary

D. LinkedList

Solution

1. Step 1: Recall DFS cycle detection method

   During DFS, we track nodes in the current recursion path to detect back edges.

2. Step 2: Identify data structure used

   This is done using a stack or a boolean array marking nodes in the recursion stack.

3. Final Answer:

   Stack or boolean array to mark recursion stack -> Option B

4. Quick Check:

   Recursion stack tracking = Stack/boolean array [OK]

Hint: Use stack or boolean array to track recursion path [OK]

Common Mistakes:

• Using queue which is FIFO, not suitable for recursion stack
• Confusing dictionary with recursion tracking
• Not marking nodes currently in recursion

3. What will be the output of the following C# code snippet detecting cycle in a directed graph?

var graph = new Dictionary<int, List<int>> {
  {1, new List<int>{2}},
  {2, new List<int>{3}},
  {3, new List<int>{1}}
};
bool HasCycle(int node, HashSet<int> visited, HashSet<int> recStack) {
  if (!visited.Contains(node)) {
    visited.Add(node);
    recStack.Add(node);
    foreach (var neighbor in graph[node]) {
      if (!visited.Contains(neighbor) && HasCycle(neighbor, visited, recStack))
        return true;
      else if (recStack.Contains(neighbor))
        return true;
    }
  }
  recStack.Remove(node);
  return false;
}

var visited = new HashSet<int>();
var recStack = new HashSet<int>();
Console.WriteLine(HasCycle(1, visited, recStack));

medium

A. False

B. Compilation error

C. Runtime exception

D. True

Solution

1. Step 1: Analyze graph edges

   The graph has edges 1->2, 2->3, and 3->1 forming a cycle.

2. Step 2: Trace DFS cycle detection

   Starting at node 1, recursion visits 2, then 3, then back to 1 which is in recursion stack, so cycle detected.

3. Final Answer:

   True -> Option D

4. Quick Check:

   Cycle exists in graph = True [OK]

Hint: Cycle if recursion stack revisits a node [OK]

Common Mistakes:

• Ignoring recursion stack check
• Assuming no cycle because graph looks simple
• Confusing visited set with recursion stack

4. Identify the bug in this C# DFS cycle detection code snippet:

bool HasCycle(int node, HashSet<int> visited, HashSet<int> recStack) {
  visited.Add(node);
  foreach (var neighbor in graph[node]) {
    if (!visited.Contains(neighbor) && HasCycle(neighbor, visited, recStack))
      return true;
    else if (recStack.Contains(neighbor))
      return true;
  }
  recStack.Remove(node);
  return false;
}

medium

A. Missing removing node from visited after recursion

B. Incorrect use of HashSet instead of List

C. Missing adding node to recStack before recursion

D. No bug, code is correct

Solution

1. Step 1: Check recursion stack usage

   Node must be added to recStack before exploring neighbors to detect back edges.

2. Step 2: Identify missing step

   Code adds node to visited but never adds to recStack before recursion, so cycle detection fails.

3. Final Answer:

   Missing adding node to recStack before recursion -> Option C

4. Quick Check:

   recStack update missing = bug [OK]

Hint: Always add node to recursion stack before DFS call [OK]

Common Mistakes:

• Forgetting to add node to recursion stack
• Removing node from visited incorrectly
• Confusing visited and recursion stack roles

5. Given a directed graph represented as adjacency list:

var graph = new Dictionary<int, List<int>> {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4}},
  {4, new List<int>{5}},
  {5, new List<int>{3}}
};

Which nodes form a cycle in this graph?

hard

A. Nodes 3, 4, 5

B. Nodes 1, 2, 4

C. Nodes 2, 3, 5

D. No cycle exists

Solution

1. Step 1: Trace edges to find cycle

   Edges: 3->4, 4->5, 5->3 form a cycle among nodes 3, 4, 5.

2. Step 2: Confirm cycle presence

   Starting at 3, path 3->4->5->3 loops back, confirming cycle.

3. Final Answer:

   Nodes 3, 4, 5 -> Option A

4. Quick Check:

   Cycle nodes = 3,4,5 [OK]

Hint: Follow edges to see if path loops back to start [OK]

Common Mistakes:

• Ignoring edge 5->3 that closes cycle
• Assuming no cycle because 1 and 2 are acyclic
• Confusing cycle nodes with all connected nodes