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#

using System;
using System.Collections.Generic;

class Graph {
    private int V;
    private 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 u, int v) {
        adj[u].Add(v);
    }

    private bool DFS(int v, bool[] visited, bool[] recStack) {
        if (!visited[v]) {
            visited[v] = true;
            recStack[v] = true;

            foreach (int neighbour in adj[v]) {
                if (!visited[neighbour] && DFS(neighbour, visited, recStack))
                    return true;
                else if (recStack[neighbour])
                    return true;
            }
        }
        recStack[v] = false;
        return false;
    }

    public bool IsCyclic() {
        bool[] visited = new bool[V];
        bool[] recStack = new bool[V];

        for (int i = 0; i < V; i++) {
            if (DFS(i, visited, recStack))
                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, 1);

        Console.WriteLine(g.IsCyclic() ? "Cycle detected" : "No cycle");
    }
}

A Cycle detected

B No cycle

C Runtime error

D Compilation 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->1. The edge 3->1 creates a cycle involving nodes 1, 2, and 3. The DFS detects this cycle and returns true, so the output is 'Cycle detected'.

❓ Predict Output

intermediate

Output when graph has no cycle

What will be the output of the following C# code that checks for cycles in a directed graph with no cycles?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private int V;
    private 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 u, int v) {
        adj[u].Add(v);
    }

    private bool DFS(int v, bool[] visited, bool[] recStack) {
        if (!visited[v]) {
            visited[v] = true;
            recStack[v] = true;

            foreach (int neighbour in adj[v]) {
                if (!visited[neighbour] && DFS(neighbour, visited, recStack))
                    return true;
                else if (recStack[neighbour])
                    return true;
            }
        }
        recStack[v] = false;
        return false;
    }

    public bool IsCyclic() {
        bool[] visited = new bool[V];
        bool[] recStack = new bool[V];

        for (int i = 0; i < V; i++) {
            if (DFS(i, visited, recStack))
                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() ? "Cycle detected" : "No cycle");
    }
}

A No cycle

B Cycle detected

C Runtime error

D Compilation error

💡 Hint

Check if any node is revisited in the current recursion stack during DFS.

The graph edges are 0->1 and 1->2, which form a linear chain with no cycles. The DFS completes without finding any back edge, so the output is 'No cycle'.

🔧 Debug

advanced

Identify the error in cycle detection code

The following code is intended to detect cycles in a directed graph using DFS. What error will it produce when run?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private int V;
    private 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 u, int v) {
        adj[u].Add(v);
    }

    private bool DFS(int v, bool[] visited, bool[] recStack) {
        if (!visited[v]) {
            visited[v] = true;
            recStack[v] = true;

            foreach (int neighbour in adj[v]) {
                if (!visited[neighbour] && DFS(neighbour, visited, recStack))
                    return true;
                else if (recStack[neighbour])
                    return true;
            }
        }
        recStack[v] = false;
        return false;
    }

    public bool IsCyclic() {
        bool[] visited = new bool[V];
        bool[] recStack = new bool[V];

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

A No error, returns correct result

B StackOverflowException

C NullReferenceException

D IndexOutOfRangeException

💡 Hint

Check the loop boundary in IsCyclic method.

The for loop in IsCyclic uses 'i <= V', which tries to access adj[V], causing IndexOutOfRangeException because valid indices are 0 to V-1.

❓ Predict Output

advanced

Output of cycle detection with multiple disconnected components

What is the output of the following C# code that detects cycles in a directed graph with multiple disconnected components?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private int V;
    private 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 u, int v) {
        adj[u].Add(v);
    }

    private bool DFS(int v, bool[] visited, bool[] recStack) {
        if (!visited[v]) {
            visited[v] = true;
            recStack[v] = true;

            foreach (int neighbour in adj[v]) {
                if (!visited[neighbour] && DFS(neighbour, visited, recStack))
                    return true;
                else if (recStack[neighbour])
                    return true;
            }
        }
        recStack[v] = false;
        return false;
    }

    public bool IsCyclic() {
        bool[] visited = new bool[V];
        bool[] recStack = new bool[V];

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

class Program {
    static void Main() {
        Graph g = new Graph(6);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(3, 4);
        g.AddEdge(4, 5);

        Console.WriteLine(g.IsCyclic() ? "Cycle detected" : "No cycle");
    }
}

A Runtime error

B No cycle

C Cycle detected

D Compilation error

💡 Hint

Check each disconnected component for cycles.

The first component (0->1->2->0) forms a cycle. The second component (3->4->5) has no cycle. Since one component has a cycle, the output is 'Cycle detected'.

🧠 Conceptual

expert

Why use recursion stack in cycle detection for directed graphs?

In cycle detection for directed graphs using DFS, why do we maintain a recursion stack (recStack) array alongside the visited array?

A To count the total number of nodes in the graph

B To detect back edges indicating a cycle in the current DFS path

C To store the order of nodes for topological sorting

D To mark nodes that have been fully processed and won't be visited again

💡 Hint

Think about how cycles appear in the current path of DFS traversal.

The recursion stack tracks nodes currently in the DFS path. If we revisit a node in this stack, it means a back edge exists, indicating a cycle. The visited array alone cannot detect this.

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