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++

vector<int> [1][V];

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

Anodes

Bgraph

Cedges

Dadj

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'graph' or 'nodes' which are less common for adjacency lists.

The adjacency list is commonly named adj to represent edges from each vertex.

2fill in blank

medium

Complete the code to mark the current node as visited in DFS.

DSA C++

visited[[1]] = true;

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

Av

Bnode

Cu

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using loop index 'i' or neighbor 'v' instead of current node 'u'.

In DFS, the current node is often named u. Marking visited[u] as true prevents revisiting.

3fill in blank

hard

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

DSA C++

if (!visited[[1]]) dfs([1], visited, adj, stack);

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

Av

Bu

Ci

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'u' causes infinite recursion or no progress.

We check and visit neighbors named v, not the current node u.

4fill in blank

hard

Fill both blanks to correctly push the node onto the stack after DFS.

DSA C++

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

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

Anode

Bstk

Cstack

Ds

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing variable names causes compilation errors.

The DFS function parameter is named node. The stack variable is stack. We push node onto stack.

5fill in blank

hard

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

DSA C++

vector<int> topologicalSort(int V, vector<int> adj[]) {
    vector<bool> visited(V, false);
    stack<int> [1];
    for (int [2] = 0; [2] < V; [2]++) {
        if (!visited[[2]]) dfs([2], visited, adj, [1]);
    }
    vector<int> order;
    while (![1].empty()) {
        order.push_back([1].top());
        [1].pop();
    }
    return order;
}

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

Astack

Bi

Attempts:

3 left

💡 Hint

Common Mistakes

Using different names for the stack causes errors.

The stack variable is named stack. The loop variable is i. We use stack consistently to store nodes.

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