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 order of nodes after performing a topological sort using DFS on the given graph?

DSA C++

/* Graph edges:
0 -> 1
0 -> 2
1 -> 3
2 -> 3
*/

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;
    for (int nbr : adj[node]) {
        if (!visited[nbr]) {
            dfs(nbr, adj, visited, st);
        }
    }
    st.push(node);
}

int main() {
    int V = 4;
    vector<vector<int>> adj(V);
    adj[0] = {1, 2};
    adj[1] = {3};
    adj[2] = {3};

    vector<bool> visited(V, false);
    stack<int> st;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited, st);
        }
    }

    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

A 1 2 0 3

B 3 1 2 0

C 0 1 2 3

D 0 2 1 3

💡 Hint

Remember that DFS pushes nodes onto the stack after visiting all descendants.

The DFS visits node 0 first, then explores node 1 and node 2. Both 1 and 2 lead to 3. The stack pushes nodes after visiting all their neighbors, so 3 is pushed first, then 1 and 2, and finally 0. The output is the reverse of the finishing times: 0 2 1 3.

❓ Predict Output

intermediate

Topological Sort Output with Multiple Independent Chains

Given the graph with edges 5->2, 5->0, 4->0, 4->1, 2->3, 3->1, what is the output of the topological sort using DFS?

DSA C++

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;
    for (int nbr : adj[node]) {
        if (!visited[nbr]) {
            dfs(nbr, adj, visited, st);
        }
    }
    st.push(node);
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    adj[5] = {2, 0};
    adj[4] = {0, 1};
    adj[2] = {3};
    adj[3] = {1};

    vector<bool> visited(V, false);
    stack<int> st;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited, st);
        }
    }

    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

A 5 4 2 3 1 0

B 5 4 0 1 2 3

C 4 5 2 3 1 0

D 4 5 0 1 2 3

💡 Hint

Nodes with no incoming edges are visited first; DFS finishes nodes after their descendants.

DFS visits node 0,1,2,3 only after visiting 4 and 5. Node 4 and 5 have no incoming edges, so they are visited first. The stack pushes nodes after all descendants are visited, resulting in the order 4 5 2 3 1 0.

🔧 Debug

advanced

Identify the Bug in DFS Topological Sort Implementation

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

DSA C++

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;
    for (int nbr : adj[node]) {
        if (visited[nbr]) {
            dfs(nbr, adj, visited, st);
        }
    }
    st.push(node);
}

int main() {
    int V = 3;
    vector<vector<int>> adj(V);
    adj[0] = {1};
    adj[1] = {2};

    vector<bool> visited(V, false);
    stack<int> st;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited, st);
        }
    }

    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

A The stack should be a queue to maintain correct order.

B The condition 'if (visited[nbr])' should be 'if (!visited[nbr])' to visit unvisited neighbors.

C The visited array should be reset after each DFS call.

D The adjacency list should be reversed before DFS.

💡 Hint

Check the condition that decides whether to recurse on neighbors.

The bug is that the code recurses only if the neighbor is already visited, which is wrong. It should recurse only if the neighbor is not visited to explore all nodes properly.

❓ Predict Output

advanced

Topological Sort Output with Cycle Detection Missing

What will be the output of the following code performing DFS-based topological sort on a graph with a cycle?

DSA C++

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;
    for (int nbr : adj[node]) {
        if (!visited[nbr]) {
            dfs(nbr, adj, visited, st);
        }
    }
    st.push(node);
}

int main() {
    int V = 3;
    vector<vector<int>> adj(V);
    adj[0] = {1};
    adj[1] = {2};
    adj[2] = {0}; // cycle here

    vector<bool> visited(V, false);
    stack<int> st;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited, st);
        }
    }

    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

A The code runs but output is not a valid topological order due to cycle.

B Runtime error due to infinite recursion.

C 0 2 1

D Compilation error due to cycle in graph.

💡 Hint

DFS without cycle detection can produce output but it won't be valid topological order if cycle exists.

The code does not detect cycles, so it runs and outputs nodes in some order. However, because the graph has a cycle, the output is not a valid topological order.

🧠 Conceptual

expert

Why DFS is Suitable for Topological Sort?

Which of the following best explains why DFS is used for topological sorting of a Directed Acyclic Graph (DAG)?

A DFS explores all descendants before the node itself, ensuring nodes are pushed after their dependencies.

B DFS uses less memory than BFS, making it faster for topological sort.

C DFS can detect cycles automatically without extra data structures.

D DFS visits nodes in increasing order of their values, which matches topological order.

💡 Hint

Think about the order nodes are added to the stack in DFS.

DFS visits all descendants of a node before pushing the node itself onto the stack. This ensures that dependencies come before dependents in the final order, which is the essence of topological sorting.

Practice

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

easy

A. To count the total number of nodes in the graph

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

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

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are processed first.

2. Step 2: Relation to dependencies in DAG

   In Topological Sort, DFS ensures nodes are ordered so that all dependencies (edges) come before the node itself.

3. Final Answer:

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

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

Hint: DFS orders nodes so dependencies appear before dependents [OK]

Common Mistakes:

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

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] = true;

C. visited[node] == true;

D. visited[node] != false;

Solution

1. Step 1: Understand C++ syntax for arrays or vectors

   To mark a node visited, we assign true to visited[node] using = operator.

2. Step 2: Analyze options for correctness

   visited[node] = true; uses correct syntax: visited[node] = true; Options A, C, D use wrong syntax or comparison operators.

3. Final Answer:

   visited[node] = true; -> Option B

4. Quick Check:

   Assignment uses =, not == or function call [OK]

Hint: Use = to assign true to visited[node] in C++ [OK]

Common Mistakes:

• Using == instead of = for assignment
• Using parentheses instead of brackets for indexing
• Using != false which is confusing and incorrect here

3. What will be the output topological order of the following graph using DFS?

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

medium

A. [0, 1, 2, 3]

B. [3, 1, 2, 0]

C. [0, 2, 1, 3]

D. [1, 0, 2, 3]

Solution

1. Step 1: Perform DFS starting from node 0

   Visit 0, then 1 and 3, then backtrack and visit 2 and 3 (already visited). The order of finishing nodes is 3,1,2,0 reversed gives topological order.

2. Step 2: Determine topological order

   Reversing finishing times gives [0, 2, 1, 3].

3. Final Answer:

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

4. Quick Check:

   DFS finishing order reversed = [0,2,1,3] [OK]

Hint: Reverse DFS finishing order for topological sort output [OK]

Common Mistakes:

• Not reversing the DFS finishing order
• Visiting nodes in wrong order
• Confusing edges direction

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

void dfs(int node, vector<bool> &visited, stack<int> &st, vector<int> adj[]) {
  visited[node] = true;
  for (auto x : adj[node]) {
    if (!visited[x])
      dfs(x, visited, st, adj);
  }
  st.push(node);
}

// Called for all nodes
for (int i = 0; i < n; i++) {
  if (!visited[i])
    dfs(i, visited, st, adj);
}

medium

A. No error; code correctly implements DFS topological sort

B. Visited array should be reset inside dfs

C. Stack should be replaced with queue

D. Nodes should be pushed to stack before recursive calls

Solution

1. Step 1: Analyze DFS function logic

   DFS marks node visited, recursively visits neighbors, then pushes node to stack after all neighbors processed.

2. Step 2: Check correctness of stack usage and visited array

   Stack is used to store nodes in finishing order, visited array is correctly used and not reset inside DFS.

3. Final Answer:

   No error; code correctly implements DFS topological sort -> Option A

4. Quick Check:

   DFS post-order push to stack is correct [OK]

Hint: Push node after recursion to stack for correct order [OK]

Common Mistakes:

• Pushing node before recursion causing wrong order
• Resetting visited inside DFS causing infinite loops
• Using queue instead of stack for topological order

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 sort using DFS?

hard

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

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

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

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

Solution

1. Step 1: Analyze dependencies from edges

   5 -> 2, 5 -> 0 mean 5 before 2 and 0; 4 -> 0, 4 -> 1 mean 4 before 0 and 1; 2 -> 3 mean 2 before 3; 3 -> 1 mean 3 before 1. So 5 and 4 come before their successors.

2. Step 2: Validate options respecting dependencies

   [5, 4, 2, 3, 1, 0] respects all edges: 5 before 2 and 0, 4 before 0 and 1, 2 before 3, 3 before 1. Others violate these orders.

3. Final Answer:

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

4. Quick Check:

   All edges respected in order [OK]

Hint: Check all edges point forward in topological order [OK]

Common Mistakes:

• Ignoring edge directions
• Placing dependent nodes before dependencies
• Assuming any order is valid