Topological Sort

Problem Statement

You’re a task sequencer ordering nodes in a directed acyclic graph (DAG) so that for every edge u→v, u comes before v. Return a valid topological order. This medium-level DFS/BFS challenge is a dependency roadmap—line ‘em up!

Example

Input: V = 4, edges = [[0,1],[0,2],[1,3],[2,3]]

Graph:

0→1
|  \
v   v
2→3

Output: [0,1,2,3] or [0,2,1,3]

Input: V = 2, edges = [[1,0]]

Output: [1,0]

Code

class Solution {
    public int[] topologicalSort(int V, int[][] edges) {
        List> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) graph.get(edge[0]).add(edge[1]);
        Stack stack = new Stack<>();
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++) {
            if (!visited[i]) dfs(graph, i, visited, stack);
        }
        int[] result = new int[V];
        for (int i = 0; i < V; i++) result[i] = stack.pop();
        return result;
    }
    private void dfs(List> graph, int node, boolean[] visited, Stack stack) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) dfs(graph, neighbor, visited, stack);
        }
        stack.push(node);
    }
}
            

from collections import defaultdict
def topological_sort(V, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    visited = [False] * V
    stack = []
    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        stack.append(node)
    for i in range(V):
        if not visited[i]:
            dfs(i)
    return stack[::-1]  # Reverse to get order
            

function topologicalSort(V, edges) {
    let graph = Array(V).fill().map(() => []);
    for (let [u, v] of edges) graph[u].push(v);
    let visited = new Array(V).fill(false);
    let stack = [];
    function dfs(node) {
        visited[node] = true;
        for (let neighbor of graph[node]) {
            if (!visited[neighbor]) dfs(neighbor);
        }
        stack.push(node);
    }
    for (let i = 0; i < V; i++) {
        if (!visited[i]) dfs(i);
    }
    return stack.reverse();
}
            

Explanation

• DFS Insight: Post-order DFS; nodes added after all dependents—reverse for topo order.
• Flow: Build graph, DFS to stack nodes after exploring children, reverse stack.
• Example Walkthrough: [0,1],[1,2] → DFS: 0→1→2, stack=[2,1,0], reverse=[0,1,2].
• BFS Alt: Kahn’s algorithm—process nodes with in-degree 0, remove edges.
• Assumption: Input is DAG; cycles would require separate check.

Note