Quick Reference O(V + E) / O(V + E)

List<Integer> topoSort(int n, int[][] edges) {
    int[] inDeg = new int[n];
    Map<Integer, List<Integer>> g = new HashMap<>();
    for (int[] e : edges) {
        g.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
        inDeg[e[1]]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) if (inDeg[i] == 0) q.add(i);
    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
        int node = q.poll();
        order.add(node);
        for (int nb : g.getOrDefault(node, List.of()))
            if (--inDeg[nb] == 0) q.add(nb);
    }
    return order.size() == n ? order : List.of();
}

func topoSort(n int, edges [][]int) []int {
    inDeg := make([]int, n)
    graph := make(map[int][]int)
    for _, e := range edges {
        graph[e[0]] = append(graph[e[0]], e[1])
        inDeg[e[1]]++
    }
    queue := []int{}
    for i := 0; i < n; i++ {
        if inDeg[i] == 0 { queue = append(queue, i) }
    }
    order := []int{}
    for len(queue) > 0 {
        node := queue[0]; queue = queue[1:]
        order = append(order, node)
        for _, nb := range graph[node] {
            inDeg[nb]--
            if inDeg[nb] == 0 { queue = append(queue, nb) }
        }
    }
    if len(order) == n { return order }
    return nil
}

def topo_sort(num_nodes, edges):
    in_degree = [0] * num_nodes
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    queue = deque([i for i in range(num_nodes) if in_degree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == num_nodes else []

fn topo_sort(n: usize, edges: &[(usize, usize)]) -> Vec<usize> {
    let mut in_deg = vec![0usize; n];
    let mut graph = vec![vec![]; n];
    for &(u, v) in edges {
        graph[u].push(v);
        in_deg[v] += 1;
    }
    let mut queue: VecDeque<_> =
        (0..n).filter(|&i| in_deg[i] == 0).collect();
    let mut order = vec![];
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &nb in &graph[node] {
            in_deg[nb] -= 1;
            if in_deg[nb] == 0 { queue.push_back(nb); }
        }
    }
    if order.len() == n { order } else { vec![] }
}

function topoSort(n: number, edges: number[][]): number[] {
    const inDeg = new Array(n).fill(0);
    const graph = new Map<number, number[]>();
    for (const [u, v] of edges) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u)!.push(v);
        inDeg[v]++;
    }
    const queue: number[] = [];
    for (let i = 0; i < n; i++)
        if (inDeg[i] === 0) queue.push(i);
    const order: number[] = [];
    while (queue.length) {
        const node = queue.shift()!;
        order.push(node);
        for (const nb of graph.get(node) ?? [])
            if (--inDeg[nb] === 0) queue.push(nb);
    }
    return order.length === n ? order : [];
}

Use when

Task scheduling with prerequisites
Course ordering
Build order / dependency resolution
Detect cycle in directed graph

Watch out

Forgetting to check for cycles (result size < V)
Wrong in-degree initialization
Using DFS topo sort but forgetting reverse at end

Pattern

Topological Sort

Order vertices in a directed acyclic graph so that every edge points forward, solving dependency and scheduling problems in O(V + E).

Step 01

What Is This Pattern?

A topological sort produces a linear ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before v in the ordering. If the graph has a cycle, no valid topological order exists.

The Core Idea

Think of tasks with prerequisites. You cannot start task B until task A finishes. Topological sort gives you a valid execution order that respects all such dependencies.

→

↗

→

Edges: A→B, A→C, B→D, C→D
Valid orders: [A, B, C, D] or [A, C, B, D]
Multiple valid orderings may exist. Both variants produce one of them.

💡

Why DAG only? If the graph contains a cycle (e.g., A→B→C→A), there is no way to place all three vertices in order. Detecting cycles is a critical part of topological sort: Kahn's algorithm detects a cycle when the output has fewer vertices than the graph, while DFS detects it via back-edges.

Step 02

When to Use It

Look for these recognition signals in the problem statement. If you spot one, topological sort is very likely the intended approach.

"prerequisites" or "dependencies"

Course scheduling, build systems, task execution order. A must finish before B.

"ordering" or "sequence from rules"

Derive a global order from pairwise ordering constraints, like alien dictionary problems.

"cycle detection" in a directed graph

Determine if a valid schedule exists. If topological sort fails, there is a cycle.

"parallel scheduling" or "minimum semesters"

BFS-based topological sort naturally groups nodes by "level," giving the minimum number of rounds.

⚡

The key clue: You have a directed graph where you need to process nodes in an order that respects all directed edges. A brute-force approach would try every permutation O(V!). Topological sort solves it in O(V + E) by systematically processing nodes with no remaining unresolved dependencies.

Step 03

Variant 1 — Kahn's Algorithm (BFS)

BFS with In-Degree

Kahn's algorithm works by repeatedly removing nodes that have zero in-degree (no remaining prerequisites). When we remove a node, we decrement the in-degree of all its neighbors. This is the most intuitive and commonly used variant.

Walkthrough: 6 nodes, 6 edges

Graph: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1. Find a valid topological order.

Initialize

Compute in-degrees. Nodes 4 and 5 have in-degree 0. Enqueue both.

Dequeue 4

Output: [4]. Neighbors: 0, 1.
in-degree[0]: 2→1still > 0
in-degree[1]: 2→1still > 0

Dequeue 5

Output: [4, 5]. Neighbors: 0, 2.
in-degree[0]: 1→0enqueue 0
in-degree[2]: 1→0enqueue 2

Dequeue 0

Output: [4, 5, 0]. Node 0 has no outgoing edges. Nothing to update.

Dequeue 2

Output: [4, 5, 0, 2]. Neighbor: 3.
in-degree[3]: 1→0enqueue 3

Dequeue 3

Output: [4, 5, 0, 2, 3]. Neighbor: 1.
in-degree[1]: 1→0enqueue 1

Dequeue 1

Output: [4, 5, 0, 2, 3, 1]. Queue is empty. All 6 nodes processed.

order:

empty

💡

Cycle detection with Kahn's: After the algorithm finishes, if the output contains fewer than V nodes, the graph has a cycle. The remaining nodes all participate in a cycle where none can reach in-degree 0.

Step 04

Variant 2 — DFS-based Topological Sort

Post-Order DFS + Reverse

Run DFS from every unvisited node. When a node's DFS finishes (all descendants processed), push it onto a stack. After all DFS calls, the stack (top to bottom) gives the topological order. This leverages the fact that a node's post-order time is always after all of its dependencies.

Same graph: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1

DFS starting from node 5, then node 4 (arbitrary unvisited order).

          DFS(5): visit 5 → DFS(0): 0 has no unvisited neighbors, push 0
        
          → DFS(2) → DFS(3) → DFS(1): 1 finished, push 1
        
          3 finished, push 3. 2 finished, push 2. 5 finished, push 5.
        
          DFS(4): neighbors 0 (visited), 1 (visited). 4 finished, push 4.
        
          Stack (top→bottom): [4, 5, 2, 3, 1, 0] ← this is the topological order.

🎯

Choosing the variant: Use Kahn's (BFS) when you need to detect cycles easily, find the lexicographically smallest order (use a min-heap), or process nodes level-by-level (e.g., minimum semesters). Use DFS when the graph is represented via adjacency lists and you want a simple recursive solution or need to detect back-edges for cycle checking.

Step 05

Template Code

Here are the annotated Java templates for both variants. Choose the one that best fits the problem constraints.

Kahn's Algorithm (BFS)

// Kahn's Algorithm — BFS-based Topological Sort
int[] topoSortKahn(int V, List<List<Integer>> adj) {
    int[] indegree = new int[V];
    for (int u = 0; u < V; u++)
        for (int v : adj.get(u))
            indegree[v]++;             // count incoming edges

    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < V; i++)
        if (indegree[i] == 0) q.offer(i); // start from zero-indegree

    int[] order = new int[V];
    int idx = 0;

    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u;              // add to result
        for (int v : adj.get(u)) {
            indegree[v]--;
            if (indegree[v] == 0)
                q.offer(v);          // new zero-indegree node
        }
    }
    return idx == V ? order : new int[0]; // empty = cycle
}

// Kahn's Algorithm — BFS-based Topological Sort
func topoSortKahn(V int, adj [][]int) []int {
    inDegree := make([]int, V)
    for u := 0; u < V; u++ {
        for _, v := range adj[u] {
            inDegree[v]++             // count incoming edges
        }
    }

    queue := make([]int, 0)
    for i := 0; i < V; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i) // start from zero-indegree
        }
    }

    order := make([]int, 0, V)

    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        order = append(order, u)     // add to result
        for _, v := range adj[u] {
            inDegree[v]--
            if inDegree[v] == 0 {
                queue = append(queue, v) // new zero-indegree node
            }
        }
    }
    if len(order) == V {
        return order
    }
    return nil // nil = cycle detected
}

# Kahn's Algorithm — BFS-based Topological Sort
from collections import deque

def topo_sort_kahn(V: int, adj: list[list[int]]) -> list[int]:
    indegree = [0] * V
    for u in range(V):
        for v in adj[u]:
            indegree[v] += 1           # count incoming edges

    q: deque[int] = deque(
        i for i in range(V) if indegree[i] == 0
    )

    order: list[int] = []

    while q:
        u = q.popleft()
        order.append(u)               # add to result
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)          # new zero-indegree node

    return order if len(order) == V else []  # empty = cycle

// Kahn's Algorithm — BFS-based Topological Sort
use std::collections::VecDeque;

impl Solution {
    pub fn topo_sort_kahn(v: usize, adj: Vec<Vec<usize>>) -> Vec<usize> {
        let mut in_degree = vec![0usize; v];
        for u in 0..v {
            for &nb in &adj[u] {
                in_degree[nb] += 1;   // count incoming edges
            }
        }

        let mut queue: VecDeque<usize> = (0..v)
            .filter(|&i| in_degree[i] == 0)
            .collect();               // start from zero-indegree

        let mut order: Vec<usize> = Vec::with_capacity(v);

        while let Some(u) = queue.pop_front() {
            order.push(u);            // add to result
            for &nb in &adj[u] {
                in_degree[nb] -= 1;
                if in_degree[nb] == 0 {
                    queue.push_back(nb); // new zero-indegree node
                }
            }
        }
        if order.len() == v { order } else { vec![] } // empty = cycle
    }
}

// Kahn's Algorithm — BFS-based Topological Sort
function topoSortKahn(V: number, adj: number[][]): number[] {
    const indegree: number[] = new Array(V).fill(0);
    for (let u = 0; u < V; u++)
        for (const v of adj[u])
            indegree[v]++;             // count incoming edges

    const queue: number[] = [];
    for (let i = 0; i < V; i++)
        if (indegree[i] === 0) queue.push(i); // start from zero-indegree

    const order: number[] = [];

    while (queue.length > 0) {
        const u = queue.shift()!;
        order.push(u);                  // add to result
        for (const v of adj[u]) {
            indegree[v]--;
            if (indegree[v] === 0)
                queue.push(v);        // new zero-indegree node
        }
    }
    return order.length === V ? order : []; // empty = cycle
}

DFS-based Topological Sort

// DFS-based Topological Sort
int[] topoSortDFS(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    Deque<Integer> stack = new ArrayDeque<>();

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

    int[] order = new int[V];
    for (int i = 0; i < V; i++)
        order[i] = stack.pop();        // reverse post-order
    return order;
}

void dfs(int u, List<List<Integer>> adj,
         boolean[] visited, Deque<Integer> stack) {
    visited[u] = true;
    for (int v : adj.get(u))
        if (!visited[v]) dfs(v, adj, visited, stack);
    stack.push(u);                    // post-order: push after children
}

// DFS-based Topological Sort
func topoSortDFS(V int, adj [][]int) []int {
    visited := make([]bool, V)
    stack := make([]int, 0, V)

    var dfs func(u int)
    dfs = func(u int) {
        visited[u] = true
        for _, v := range adj[u] {
            if !visited[v] {
                dfs(v)
            }
        }
        stack = append(stack, u)     // post-order: push after children
    }

    for i := 0; i < V; i++ {
        if !visited[i] {
            dfs(i)
        }
    }

    // reverse stack in-place
    for lo, hi := 0, len(stack)-1; lo < hi; lo, hi = lo+1, hi-1 {
        stack[lo], stack[hi] = stack[hi], stack[lo]
    }
    return stack // reverse post-order
}

# DFS-based Topological Sort
def topo_sort_dfs(V: int, adj: list[list[int]]) -> list[int]:
    visited = [False] * V
    stack: list[int] = []

    def dfs(u: int) -> None:
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)               # post-order: push after children

    for i in range(V):
        if not visited[i]:
            dfs(i)

    return stack[::-1]               # reverse post-order

// DFS-based Topological Sort
impl Solution {
    pub fn topo_sort_dfs(v: usize, adj: Vec<Vec<usize>>) -> Vec<usize> {
        let mut visited = vec![false; v];
        let mut stack: Vec<usize> = Vec::with_capacity(v);

        fn dfs(
            u: usize,
            adj: &Vec<Vec<usize>>,
            visited: &mut Vec<bool>,
            stack: &mut Vec<usize>,
        ) {
            visited[u] = true;
            for &nb in &adj[u] {
                if !visited[nb] {
                    dfs(nb, adj, visited, stack);
                }
            }
            stack.push(u);             // post-order: push after children
        }

        for i in 0..v {
            if !visited[i] {
                dfs(i, &adj, &mut visited, &mut stack);
            }
        }
        stack.reverse();               // reverse post-order
        stack
    }
}

// DFS-based Topological Sort
function topoSortDFS(V: number, adj: number[][]): number[] {
    const visited: boolean[] = new Array(V).fill(false);
    const stack: number[] = [];

    for (let i = 0; i < V; i++)
        if (!visited[i]) dfs(i, adj, visited, stack);

    return stack.reverse();           // reverse post-order
}

function dfs(u: number, adj: number[][],
             visited: boolean[], stack: number[]): void {
    visited[u] = true;
    for (const v of adj[u])
        if (!visited[v]) dfs(v, adj, visited, stack);
    stack.push(u);                    // post-order: push after children
}

📝

Cycle detection in DFS: Add a visiting[] (gray) array alongside visited[] (black). If you encounter a node that is currently in the "visiting" state, you have found a back-edge, which means a cycle exists. Return false immediately.

Step 06

Visual Walkthrough

Let us trace through Kahn's algorithm on a different graph step by step, showing the queue, in-degrees, and output at every stage.

Graph: 4 nodes, edges: 0→1, 0→2, 1→3, 2→3

A classic diamond DAG. Node 0 has no prerequisites. Node 3 depends on both 1 and 2.

STEP	ACTION	QUEUE	IN-DEGREES	OUTPUT
Init	Compute in-degrees, enqueue 0	[0]	[0:0, 1:1, 2:1, 3:2]	[]
1	Dequeue 0, decrement 1 and 2	[1, 2]	0:0, 1:0, 2:0, 3:2	[0]
2	Dequeue 1, decrement 3	[2]	3:1	[0, 1]
3	Dequeue 2, decrement 3	[3]	3:0	[0, 1, 2]
4	Dequeue 3, no neighbors	[]	all zero	[0, 1, 2, 3]

order:

💡

Notice the pattern: Each vertex is enqueued exactly once (when its in-degree hits 0) and dequeued exactly once. Each edge is examined exactly once (when we decrement in-degrees). Total work: O(V + E).

Step 07

Common Problems

These are the classic LeetCode problems that use topological sort, listed in rough order of difficulty.

#207 Course Schedule Medium

#210 Course Schedule II Medium

#802 Find Eventual Safe States Medium

#310 Minimum Height Trees Medium

#1136 Parallel Courses Medium

#269 Alien Dictionary Hard

💡

Practice tip: Start with #207 (pure cycle detection via topological sort) and #210 (return the actual order). Once comfortable, try #269 which requires you to build the graph from character comparisons before applying topological sort. #1136 uses BFS topological sort level-by-level to find the minimum number of semesters.

Step 08

Interactive Demo

Define edges of a DAG and step through Kahn's algorithm. Watch in-degrees update, the queue fill and drain, and the output order build up.

⚙ Topological Sort Visualizer

Nodes

Edges (u,v pairs)

IN-DEGREES

OUTPUT ORDER

Press "Step →" or "Run All" to begin.

Step 09

Complexity Analysis

Time

O(V + E)

Space

O(V + E)

Why O(V + E)?

Both Kahn's and DFS variants visit every vertex exactly once and examine every edge exactly once. Computing in-degrees requires iterating all edges: O(E). The BFS loop processes each vertex once O(V) and each edge once O(E) when decrementing in-degrees. Total: O(V + E).

Space: The adjacency list takes O(V + E). The in-degree array and queue (or visited array and recursion stack) take O(V). The output array takes O(V). Total: O(V + E).

⚡

Kahn's vs DFS performance: Both are O(V + E). Kahn's uses a queue (iterative, no stack overflow risk). DFS uses recursion, which can hit stack limits on very deep graphs with hundreds of thousands of nodes. For large inputs, prefer Kahn's or convert DFS to iterative form.

Step 10

Key Takeaways

DAG = Topological Sort exists. A topological ordering exists if and only if the graph is a DAG (directed acyclic graph). Both algorithms double as cycle detectors: Kahn's checks output size, DFS checks for back-edges.

Kahn's for BFS-level grouping and cycle detection. Kahn's algorithm naturally provides the "level" (distance from sources) of each node, making it ideal for problems like "minimum semesters" or "parallel task scheduling."

DFS for simple recursive implementation. DFS-based topological sort is concise and works well when cycle detection is done separately or when you need post-order processing. Add a "visiting" state for three-color cycle detection.

Build the graph first. Many problems do not give you an explicit adjacency list. You must construct the graph from the problem description (e.g., character ordering in Alien Dictionary, prerequisite pairs in Course Schedule).

Use a min-heap for lexicographic order. If the problem asks for the lexicographically smallest topological order, replace the queue in Kahn's algorithm with a priority queue (min-heap). This ensures you always process the smallest available node first.