Topological Sort Using DFS 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'

Aedges

B5

Cnodes

Dvertices

Attempts:

3 left

💡 Hint

Common Mistakes

Using number of edges instead of vertices for array size.

Using variable names instead of actual size.

The adjacency list array size should be the number of vertices, here 5.

2fill in blank

medium

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

DSA C#

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

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

Au

Bv

Cgraph

Dedges

Attempts:

3 left

💡 Hint

Common Mistakes

Adding u to v's list instead of v to u's list.

Using wrong variable names.

We add v to the adjacency list of u to represent an edge u -> v.

3fill in blank

hard

Fix the error in the DFS function call to visit neighbors.

DSA C#

foreach (int neighbor in graph[node])
{
    if (!visited[neighbor])
    {
        DFS([1], visited, stack, graph);
    }
}

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

Aneighbor

Bnode

Cvisited

Dstack

Attempts:

3 left

💡 Hint

Common Mistakes

Calling DFS on the same node repeatedly.

Passing wrong parameters to DFS.

We must call DFS on the neighbor node, not the current node.

4fill in blank

hard

Fill both blanks to correctly push the node after visiting neighbors and mark it visited.

DSA C#

visited[[1]] = true;
stack.[2](node);

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

Anode

Bneighbor

CPush

DPop

Attempts:

3 left

💡 Hint

Common Mistakes

Marking neighbor visited instead of node.

Using Pop instead of Push on stack.

Mark the current node visited and push it onto the stack after DFS.

5fill in blank

hard

Fill all three blanks to create the topological sort function using DFS.

DSA C#

public static List<int> TopologicalSort(List<int>[] graph, int [1])
{
    bool[] visited = new bool[[2]];
    Stack<int> stack = new Stack<int>();
    for (int i = 0; i < [3]; i++)
    {
        if (!visited[i])
            DFS(i, visited, stack, graph);
    }
    List<int> result = new List<int>();
    while (stack.Count > 0)
        result.Add(stack.Pop());
    return result;
}

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

An

Bgraph.Length

Dvisited.Length

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable names for sizes.

Looping beyond graph length.

Use n as parameter and loop limit, graph.Length for visited array size.

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