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 topological sort using DFS on the given graph?

The graph edges are:
0 -> 1
0 -> 2
1 -> 3
2 -> 3

DSA C

void dfs(int node, int visited[], int stack[], int *top, int graph[][4]) {
    visited[node] = 1;
    for (int i = 0; i < 4; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(i, visited, stack, top, graph);
        }
    }
    stack[(*top)++] = node;
}

int main() {
    int graph[4][4] = {
        {0,1,1,0},
        {0,0,0,1},
        {0,0,0,1},
        {0,0,0,0}
    };
    int visited[4] = {0};
    int stack[4];
    int top = 0;
    for (int i = 0; i < 4; i++) {
        if (!visited[i]) dfs(i, visited, stack, &top, graph);
    }
    for (int i = top - 1; i >= 0; i--) {
        printf("%d ", stack[i]);
    }
    return 0;
}

A 3 1 2 0

B 0 2 1 3

C 0 1 2 3

D 1 0 2 3

💡 Hint

Remember that DFS pushes nodes to stack after visiting all descendants.

DFS visits 0 first, then explores 1 and 2. Both 1 and 2 lead to 3. The stack ends up with nodes in order 3,1,2,0 pushed, so output reversed is 0 2 1 3.

🧠 Conceptual

intermediate

Understanding the Role of the Stack in DFS Topological Sort

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

A Because it reduces the time complexity of DFS.

B Because it helps to detect cycles in the graph.

C Because it ensures nodes are output in the order they are first visited.

D Because it guarantees that all dependencies of a node are processed before the node itself.

💡 Hint

Think about the meaning of dependencies in a directed graph.

Pushing nodes after visiting all neighbors ensures that all nodes that depend on the current node are placed before it in the output, preserving dependency order.

🔧 Debug

advanced

Identify the Error in This DFS Topological Sort Implementation

What error will this code produce when running DFS topological sort on a graph with 3 nodes and edges 0->1, 1->2?

Code snippet:
void dfs(int node, int visited[], int stack[], int *top, int graph[][3]) { visited[node] = 1; for (int i = 0; i < 3; i++) { if (graph[node][i] && visited[i] == 0) { dfs(i, visited, stack, top, graph); } } stack[*top] = node; (*top)++; } int main() { int graph[3][3] = { {0,1,0}, {0,0,1}, {0,0,0} }; int visited[3] = {0}; int stack[3]; int top = 0; for (int i = 0; i < 3; i++) { if (!visited[i]) dfs(i, visited, stack, &top, graph); } for (int i = 0; i < top; i++) { printf("%d ", stack[i]); } return 0; }

A The output order is reversed; it prints nodes in finishing order, not topological order.

B The code causes a segmentation fault due to stack overflow.

C The code prints nodes in correct topological order.

D The code causes a syntax error due to missing semicolons.

💡 Hint

Check how the stack is printed compared to how nodes are pushed.

The code prints the stack from index 0 to top-1, which is the order nodes were pushed (finishing order). Topological order requires printing in reverse order.

🚀 Application

advanced

Find a Valid Topological Order for a Complex DAG

Given the directed edges:
5 -> 2
5 -> 0
4 -> 0
4 -> 1
2 -> 3
3 -> 1

Which of the following is a valid topological order?

A 4 5 0 2 3 1

B 5 2 4 3 1 0

C 5 4 2 3 1 0

D 2 3 5 4 1 0

💡 Hint

Remember that a node must come before all nodes it points to.

Option C respects all edges: 5 before 2 and 0, 4 before 0 and 1, 2 before 3, and 3 before 1.

🧠 Conceptual

expert

Detecting Cycles in DFS-based Topological Sort

In a DFS-based topological sort, how can you detect a cycle in the graph during traversal?

A If a node is found in the recursion stack (currently being visited), a cycle exists.

B If the stack size is less than the number of nodes, a cycle exists.

C If a node is visited twice during DFS, a cycle exists.

D If the graph has more edges than nodes, a cycle exists.

💡 Hint

Think about nodes currently in the path of DFS recursion.

A cycle is detected if during DFS we visit a node that is already in the current recursion path (recursion stack).

Practice

1. What is the main purpose of using DFS in Topological Sort on a Directed Acyclic Graph (DAG)?

easy

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

B. To find the shortest path between two nodes

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 to dependency order

   This ensures nodes appear after all their dependencies, which is the goal of topological sorting.

3. Final Answer:

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

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

Hint: DFS ensures dependencies come before nodes in topological order [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking DFS detects cycles in undirected graphs here
• Mixing connected components with topological order

2. Which of the following is the correct way to mark a node as visited in a DFS-based topological sort in C?

easy

A. visited(node) = true;

B. visited[node] = 1;

C. visited[node] == true;

D. visited[node] = false;

Solution

1. Step 1: Understand C syntax for arrays

   In C, arrays use square brackets to access elements, so visited[node] is correct.

2. Step 2: Assigning visited status

   Assigning 1 marks the node as visited; '==' is comparison, not assignment; 'false' would mark unvisited.

3. Final Answer:

   visited[node] = 1; -> Option B

4. Quick Check:

   Use visited[node] = 1 to mark visited [OK]

Hint: Use visited[node] = 1 to mark visited in C arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Using '==' instead of '=' for assignment
• Assigning false instead of true/1 to mark visited

3. What is the output order of nodes after performing DFS-based topological sort on this graph?

Edges:
0 -> 1
0 -> 2
1 -> 3
2 -> 3

Assume nodes are pushed to stack after visiting all neighbors and stack is printed top to bottom.

medium

A. [0, 2, 1, 3]

B. [3, 2, 1, 0]

C. [0, 1, 2, 3]

D. [3, 1, 2, 0]

Solution

1. Step 1: Perform DFS starting from node 0

   Visit 0, then neighbors 1 then 2 (edge order). From 1 to 3, from 2 to 3 (visited).

2. Step 2: Push nodes to stack after visiting neighbors

   Push 3, then 1, then 3 already visited, then 2, then 0. Stack top to bottom: [3, 1, 2, 0].

3. Final Answer:

   [3, 1, 2, 0] -> Option D

4. Quick Check:

   Stack top to bottom after DFS = [3, 1, 2, 0] [OK]

Hint: Push nodes after neighbors; output is stack top to bottom [OK]

Common Mistakes:

• Pushing nodes before visiting neighbors
• Confusing order of neighbors visited
• Printing stack bottom to top instead of top to bottom

4. Identify the error in this DFS-based topological sort code snippet in C:

void dfs(int node) {
  visited[node] = 1;
  for (int i = 0; i < adj[node].size(); i++) {
    int nbr = adj[node][i];
    if (!visited[nbr])
      dfs(nbr);
  }
  stack.push(node);
}

medium

A. Stack push should be before recursive calls

B. Missing base case for cycle detection

C. Using adj[node].size() is invalid in C

D. visited array should be initialized to 2 instead of 1

Solution

1. Step 1: Check syntax for adjacency list size in C

   adj[node].size() is C++ syntax; C does not support .size() method on arrays.

2. Step 2: Identify correct way to get adjacency list size in C

   In C, adjacency lists are usually arrays with separate size variables; .size() causes compile error.

3. Final Answer:

   Using adj[node].size() is invalid in C -> Option C

4. Quick Check:

   adj[node].size() is C++ only, not C [OK]

Hint: Use array length variables in C, not .size() method [OK]

Common Mistakes:

• Confusing C and C++ syntax for containers
• Ignoring cycle detection in topological sort
• Pushing nodes before recursive calls

5. Given a graph with edges:

5 -> 2
5 -> 0
4 -> 0
4 -> 1
2 -> 3
3 -> 1

Which of the following is a valid topological order using DFS-based topological sort?

hard

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

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

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

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

Solution

1. Step 1: Analyze prerequisites from edges

   (u -> v means u before v): 5 before 2 and 0; 4 before 0 and 1; 2 before 3; 3 before 1.

2. Step 2: Check each option for prerequisite order

   [4, 5, 2, 3, 1, 0]: 4 before 0 and 1, 5 before 2 and 0, 2 before 3, 3 before 1, all correct.

3. Final Answer:

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

4. Quick Check:

   All edges respected in order D [OK]

Hint: Check each edge u->v: u appears before v in order [OK]

Common Mistakes:

• Ignoring edge directions in order
• Placing dependent nodes before their prerequisites
• Assuming any order with all nodes is valid