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).