Topological Sort Using DFS in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Topological Sort on a Simple DAG

What is the output of the following C# code performing a topological sort using DFS on the given graph?

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 v, int w) {
        adj[v].Add(w);
    }

    private void DFS(int v, bool[] visited, Stack<int> stack) {
        visited[v] = true;
        foreach (int i in adj[v]) {
            if (!visited[i]) {
                DFS(i, visited, stack);
            }
        }
        stack.Push(v);
    }

    public void TopologicalSort() {
        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                DFS(i, visited, stack);
            }
        }

        while (stack.Count > 0) {
            Console.Write(stack.Pop() + " ");
        }
    }
}

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

        g.TopologicalSort();
    }
}

A 0 1 2 3 4 5

B 5 4 2 3 1 0

C 4 5 0 2 3 1

D 5 2 3 4 1 0

💡 Hint

Remember that in topological sort using DFS, nodes are pushed to stack after visiting all their descendants.

The DFS visits nodes starting from 5 and 4, pushing nodes to stack after visiting all reachable nodes. The correct topological order is 5 4 2 3 1 0.

🧠 Conceptual

intermediate

Understanding the Role of Stack in DFS Topological Sort

In the DFS-based topological sort algorithm, why do we push the node onto the stack only after visiting all its neighbors?

A To guarantee that all dependencies of a node appear before the node in the final order.

B To store nodes in the order they are discovered during traversal.

C To avoid revisiting nodes multiple times during DFS.

D To ensure nodes are output in the order they are first visited.

💡 Hint

Think about the dependency relationship in a directed acyclic graph.

Pushing nodes after visiting all neighbors ensures that all nodes that depend on the current node are placed before it in the final order, respecting dependencies.

❓ Predict Output

advanced

Detecting Cycle Impact on Topological Sort Output

What will be the output or error when running this C# code that attempts a topological sort on a graph with a cycle?

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 v, int w) {
        adj[v].Add(w);
    }

    private bool DFS(int v, bool[] visited, bool[] recStack, Stack<int> stack) {
        visited[v] = true;
        recStack[v] = true;

        foreach (int i in adj[v]) {
            if (!visited[i]) {
                if (DFS(i, visited, recStack, stack)) return true;
            } else if (recStack[i]) {
                return true; // cycle detected
            }
        }

        recStack[v] = false;
        stack.Push(v);
        return false;
    }

    public void TopologicalSort() {
        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[V];
        bool[] recStack = new bool[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (DFS(i, visited, recStack, stack)) {
                    Console.WriteLine("Cycle detected, topological sort not possible");
                    return;
                }
            }
        }

        while (stack.Count > 0) {
            Console.Write(stack.Pop() + " ");
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(3);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0); // cycle here

        g.TopologicalSort();
    }
}

A Cycle detected, topological sort not possible

B 0 1 2

C 2 1 0

D Runtime error due to infinite recursion

💡 Hint

Check how the code detects cycles using recursion stack.

The code detects a cycle using the recursion stack and prints the message instead of producing a topological order.

🔧 Debug

advanced

Identify the Bug in DFS Topological Sort Implementation

What is the bug in this DFS-based topological sort code snippet that causes incorrect output?

DSA C#

private void DFS(int v, bool[] visited, Stack<int> stack) {
    visited[v] = true;
    foreach (int i in adj[v]) {
        if (!visited[i]) {
            DFS(i, visited, stack);
        }
        stack.Push(v);
    }
}

A The adjacency list is not being iterated correctly.

B visited array is not initialized before DFS calls.

C DFS does not mark nodes as visited.

D stack.Push(v) is inside the foreach loop, causing multiple pushes of the same node.

💡 Hint

Consider when nodes should be pushed to the stack in DFS topological sort.

Pushing the node inside the loop causes it to be pushed multiple times, leading to incorrect topological order.

🚀 Application

expert

Topological Sort Output for Complex Graph

Given the following directed acyclic graph edges, what is the topological sort output using DFS? Edges: 0 -> 1 0 -> 2 1 -> 3 2 -> 3 3 -> 4 4 -> 5 2 -> 5

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 v, int w) {
        adj[v].Add(w);
    }

    private void DFS(int v, bool[] visited, Stack<int> stack) {
        visited[v] = true;
        foreach (int i in adj[v]) {
            if (!visited[i]) {
                DFS(i, visited, stack);
            }
        }
        stack.Push(v);
    }

    public void TopologicalSort() {
        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                DFS(i, visited, stack);
            }
        }

        while (stack.Count > 0) {
            Console.Write(stack.Pop() + " ");
        }
    }
}

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

        g.TopologicalSort();
    }
}

A 0 1 2 3 4 5

B 5 4 3 2 1 0

C 0 2 1 3 4 5

D 0 2 5 1 3 4

💡 Hint

Trace DFS calls starting from node 0 and remember nodes are pushed after visiting all descendants.

The DFS visits nodes in order 0, then 1 and 2, exploring their descendants. The correct topological order is 0 2 1 3 4 5.

Practice

1. What is the main purpose of using DFS in Topological Sort on a directed graph?

easy

A. To find the shortest path between two nodes

B. To visit nodes in a way that all dependencies come before the node itself

C. To detect cycles in an undirected graph

D. To count the number of connected components

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are visited before the node itself.

2. Step 2: Relate DFS order to dependencies

   In Topological Sort, nodes must appear after all their dependencies, which DFS achieves by post-order traversal.

3. Final Answer:

   To visit nodes in a way that all dependencies come before the node itself -> Option B

4. Quick Check:

   DFS ensures dependency order [OK]

Hint: DFS post-order gives correct dependency order [OK]

Common Mistakes:

• Confusing DFS with BFS for topological sorting
• Thinking DFS finds shortest paths
• Assuming DFS detects cycles in undirected graphs only

2. Which of the following C# code snippets correctly starts a DFS-based topological sort on all nodes in a graph represented as adjacency list Dictionary?

easy

A. for(int i=0; i

B. while(graph.Count > 0) DFS(graph.First().Key);

C. foreach(var node in graph.Keys) if(!visited[node]) DFS(node);

D. foreach(var node in graph.Values) DFS(node[0]);

Solution

1. Step 1: Identify correct iteration over nodes

   We must iterate over all keys (nodes) and call DFS only if not visited.

2. Step 2: Check each option's correctness

   foreach(var node in graph.Keys) if(!visited[node]) DFS(node); correctly iterates keys and checks visited. for(int i=0; i 0) DFS(graph.First().Key); modifies graph during iteration, unsafe. foreach(var node in graph.Values) DFS(node[0]); iterates values, not nodes.

3. Final Answer:

   foreach(var node in graph.Keys) if(!visited[node]) DFS(node); -> Option C

4. Quick Check:

   Iterate keys and check visited [OK]

Hint: Iterate graph keys, check visited before DFS [OK]

Common Mistakes:

• Iterating over graph.Values instead of Keys
• Assuming node indices are continuous from 0
• Modifying collection during iteration

3. What is the output of the following C# code performing topological sort using DFS on the graph edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1?

var graph = new Dictionary {
  {5, new List<int>{2,0}},
  {4, new List<int>{0,1}},
  {2, new List<int>{3}},
  {3, new List<int>{1}},
  {0, new List<int>()},
  {1, new List<int>()}
};
var visited = new HashSet<int>();
var stack = new Stack<int>();
void DFS(int node) {
  visited.Add(node);
  foreach(var n in graph[node]) {
    if(!visited.Contains(n)) DFS(n);
  }
  stack.Push(node);
}
foreach(var node in graph.Keys) {
  if(!visited.Contains(node)) DFS(node);
}
var result = stack.ToArray();
Console.WriteLine(string.Join(", ", result));

medium

A. 4, 5, 0, 2, 3, 1

B. 5, 4, 2, 3, 1, 0

C. 5, 4, 0, 1, 2, 3

D. 4, 5, 0, 1, 2, 3

Solution

1. Step 1: Perform DFS and track stack push order

   Start DFS from 5: visit 2, then 3, then 1; push 1, 3, 2, then 0 from 5's other edge; push 5. Then DFS from 4: visit 0 and 1 already visited, push 4.

2. Step 2: Stack order and output

   Stack push order is 1, 3, 2, 0, 5, 4. Converting stack to array reverses order: 4, 5, 0, 2, 3, 1.

3. Final Answer:

   4, 5, 0, 2, 3, 1 -> Option A

4. Quick Check:

   DFS post-order reversed = topological order [OK]

Hint: Stack reversed after DFS gives topological order [OK]

Common Mistakes:

• Not reversing stack before output
• Visiting nodes in wrong order
• Ignoring nodes with no outgoing edges

4. The following C# DFS-based topological sort code throws a runtime error. What is the likely cause?

void DFS(int node) {
  visited.Add(node);
  foreach(var n in graph[node]) {
    if(!visited.Contains(n)) DFS(n);
  }
  stack.Push(node);
}
foreach(var node in graph.Keys) {
  DFS(node);
}

medium

A. No error; code runs correctly

B. NullReferenceException because graph is empty

C. Stack overflow due to infinite recursion from cycles

D. KeyNotFoundException because some nodes are missing in graph keys

Solution

1. Step 1: Analyze potential runtime errors in DFS

   When recursing to a neighbor n not present as a key in the graph (common for sink nodes), accessing graph[n] throws KeyNotFoundException.

2. Step 2: Outer loop issue

   Missing !visited check before DFS(node) causes duplicate stack pushes (logical error), not runtime error. Cycle detection needs separate recursion stack.

3. Final Answer:

   KeyNotFoundException because some nodes are missing in graph keys -> Option D

4. Quick Check:

   graph[n] for missing sink node key -> KeyNotFoundException [OK]

Hint: Include all nodes as keys with empty lists [OK]

Common Mistakes:

• Omitting sink/leaf nodes from graph keys
• Not initializing empty List<int>() for nodes with no outgoing edges
• Assuming all edge targets are automatically graph keys

5. Given a directed acyclic graph (DAG) with nodes representing tasks and edges representing dependencies, how can you modify the DFS-based topological sort to detect if the graph contains a cycle?

hard

A. Use an additional recursion stack set to track nodes in the current DFS path and detect back edges

B. Count the number of nodes visited and compare with total nodes after DFS

C. Run BFS instead of DFS to detect cycles

D. Sort nodes by their degree before DFS

Solution

1. Step 1: Understand cycle detection in DFS

   Use a recursion stack set to mark nodes currently in the DFS path. If a node is revisited while in this set, a cycle exists.

2. Step 2: Explain why other options fail

   Counting visited nodes doesn't detect cycles. BFS alone doesn't detect cycles in directed graphs. Sorting by degree doesn't help detect cycles.

3. Final Answer:

   Use an additional recursion stack set to track nodes in the current DFS path and detect back edges -> Option A

4. Quick Check:

   Recursion stack detects cycles in DFS [OK]

Hint: Track recursion stack to find back edges indicating cycles [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming BFS detects cycles in directed graphs
• Using node count to detect cycles