What is the brute force approach and complexity for Topological Sort (template)?

Each round, recount in-degrees and place the first free vertex with time complexity O(V · (V + E)) and space complexity O(V).

What is the optimal approach and complexity for Topological Sort (template)?

Queue every in-degree 0 vertex; placing one lowers its children's in-degree with optimal time complexity O(V + E) and space complexity O(V + E).

How do you identify the pattern for Topological Sort (template)?

Look for key signals in the prompt: "directed graph with no cycles (DAG)" indicates Edges have a direction and there is no loop, so some vertex must have no parents.; "every edge goes forward in the order" indicates Each vertex must come after all its parents, so the first vertex has in-degree 0.; "any valid order is accepted" indicates We need one order that respects every edge, not one exact answer. Kahn's queue gives one of many..

Topological Sort (template)

Easy·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelTopological Sort — Kahn's algorithm (BFS on in-degree 0)

Complexity:O(V · (V + E))→O(V + E)

Key Insight

Count each vertex's in-degree once. Put every vertex with in-degree 0 in a queue. Pop a vertex, add it to the order, and lower the in-degree of each of its children by one. A child whose in-degree reaches 0 joins the queue. Nothing is ever recounted.

Core Validity Invariant

A vertex is safe to place when its in-degree is 0, which means every one of its parents is already in the order. So every edge into it already points forward.

Problem

You are given a directed acyclic graph (a DAG) with V vertices, numbered 0 to V − 1. Its E edges are given as a list edges, where edges[i] = [u, v] is an edge from u to v.

Return a list of all the vertices so that for every edge u → v, the vertex u comes before v in the list. A list like this is a topological order.

Many orders can be correct. Any one of them is accepted.

Input

V, the number of vertices, and edges, a list of directed edges [u, v].

Output

A list of all V vertices in a topological order.

Example 1

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

Output: [3, 1, 2, 0]

Vertex 0 has three parents (3, 1 and 2), so it must come last. The other three can be in any order. Any order that ends with 0 is correct.

Example 2

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

Output: [4, 5, 1, 2, 0, 3]

Vertices 4 and 5 have no parents, so they go first. In this list every edge points forward: 4 → 1, 4 → 0, 5 → 0, 5 → 2, 1 → 3 and 2 → 3.

Constraints

• 2 ≤ V ≤ 5 × 10^3
• 1 ≤ E = edges.size() ≤ min(10^5, V · (V − 1) / 2)
• 0 ≤ edges[i][0], edges[i][1] < V
• The graph has no cycles.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If an edge u → v says u must come before v, which vertex can I place first with no risk at all?
2.
What does it mean for a vertex to have no incoming edges?
3.
After I place a vertex, which other vertices might become safe to place?
4.
How do I know when every vertex is placed, and what does it mean if I get stuck with some left?
5.
A plain DFS visit order also lists every vertex. Does it respect every edge? Try it on a small example.

Brute force approach

Idea

Keep the list of vertices not placed yet. In each round, count every unplaced vertex's unplaced parents from scratch, place the first vertex that has none, and repeat until all V vertices are placed.

Thinking process

1
Every edge u → v means u must be placed before v. So the first vertex we place must have no parent at all.
2
Round 1 on V = 6, edges 5→2, 5→0, 4→0, 4→1, 2→3, 3→1: the in-degrees are 0:2, 1:2, 2:1, 3:1, 4:0, 5:0. The first free vertex is 4.
3
Round 2: 4 is placed, so the edges leaving it no longer count. Now 5 is free (in-degree 0) and is placed.
4
Round 3: both parents of 0 (4 and 5) are placed, so 0 is free and is placed. Keep going until all 6 are placed: order 4, 5, 0, 2, 3, 1.

Visual

Purple = the node picked this round, green = placed earlier. Notes show the in-degree recounted this round (placed parents are ignored).

Brute force: recount in-degrees every roundV = 6, edges = [[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]]step 1/13

graph

order

Round

round: 1
edges scanned: 6
checks so far: 12

Round 1: recount every in-degree, ignoring placed parents

Round 1 starts from scratch. We walk all 6 edges again and count only parents that are not placed. Those counts are in the node notes now.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> topoSort(int V, vector<vector<int>>& edges) {
        vector<bool> placed(V, false);
        vector<int> order;

        // One node per round. Every round starts from scratch.
        while ((int)order.size() < V) {
            // Recount in-degrees. Only edges whose start is still unplaced count.
            vector<int> indeg(V, 0);
            for (auto& e : edges)
                if (!placed[e[0]]) indeg[e[1]]++;

            // A node with no unplaced parent is safe to place next.
            int pick = -1;
            for (int v = 0; v < V; v++) {
                if (!placed[v] && indeg[v] == 0) { pick = v; break; }
            }
            if (pick == -1) break;   // cannot happen for a DAG

            placed[pick] = true;
            order.push_back(pick);
        }
        return order;
    }
};

import java.util.*;

class Solution {
    public int[] topoSort(int V, int[][] edges) {
        boolean[] placed = new boolean[V];
        int[] order = new int[V];
        int size = 0;

        // One node per round. Every round starts from scratch.
        while (size < V) {
            // Recount in-degrees. Only edges whose start is still unplaced count.
            int[] indeg = new int[V];
            for (int[] e : edges) {
                if (!placed[e[0]]) {
                    indeg[e[1]]++;
                }
            }

            // A node with no unplaced parent is safe to place next.
            int pick = -1;
            for (int v = 0; v < V; v++) {
                if (!placed[v] && indeg[v] == 0) {
                    pick = v;
                    break;
                }
            }
            if (pick == -1) break;   // cannot happen for a DAG

            placed[pick] = true;
            order[size++] = pick;
        }
        return order;
    }
}

from typing import List

class Solution:
    def topoSort(self, V: int, edges: List[List[int]]) -> List[int]:
        placed = [False] * V
        order: List[int] = []

        # One node per round. Every round starts from scratch.
        while len(order) < V:
            # Recount in-degrees. Only edges whose start is still unplaced count.
            indeg = [0] * V
            for u, v in edges:
                if not placed[u]:
                    indeg[v] += 1

            # A node with no unplaced parent is safe to place next.
            pick = -1
            for v in range(V):
                if not placed[v] and indeg[v] == 0:
                    pick = v
                    break
            if pick == -1:
                break   # cannot happen for a DAG

            placed[pick] = True
            order.append(pick)

        return order

export function topoSort(V: number, edges: number[][]): number[] {
    const placed: boolean[] = new Array(V).fill(false);
    const order: number[] = [];

    // One node per round. Every round starts from scratch.
    while (order.length < V) {
        // Recount in-degrees. Only edges whose start is still unplaced count.
        const indeg: number[] = new Array(V).fill(0);
        for (const [u, v] of edges) {
            if (!placed[u]) {
                indeg[v]++;
            }
        }

        // A node with no unplaced parent is safe to place next.
        let pick = -1;
        for (let v = 0; v < V; v++) {
            if (!placed[v] && indeg[v] === 0) {
                pick = v;
                break;
            }
        }
        if (pick === -1) break;   // cannot happen for a DAG

        placed[pick] = true;
        order.push(pick);
    }
    return order;
}

Complexity

Time O(V · (V + E))Space O(V)

There are V rounds. Each round reads all E edges to recount in-degrees and scans the V vertices, so the work is V · (V + E). With V = 5·10^3 and E = 10^5, that is about 5·10^8 steps, which is far too slow. Kahn's queue (next approach) does the same job in one pass.

Optimized approach

Idea

Start from brute force

The brute force throws its in-degree counts away after every round and rebuilds them from scratch. Most of that counting repeats work that was already done.

Find the repeated work

Placing one vertex only changes the in-degree of its children. Every other vertex keeps the same count, yet the brute reads all E edges again every round.

Define the state — what variables do I need?

indeg[v]: Number of parents of v that are not placed yet. It starts as the real in-degree.
queue: Vertices with indeg = 0 that are ready to be placed.
order: Vertices placed so far, in the order they left the queue.

Define validity

A vertex is safe to place when its in-degree is 0, which means every one of its parents is already in the order. So every edge into it already points forward.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

For every edge u → v, add 1 to indeg[v]. Queue every vertex with indeg 0.

These vertices have no parents, so they can go first. Counting once is enough, because the counts are lowered as we go.

Pop u from the queue

Add u to order. For each child v of u: indeg[v]−−. If indeg[v] is now 0, push v.

u is placed, so every edge u → v is satisfied. v becomes free only when its last parent is placed.

What does the current window add to the answer?

Each vertex is pushed exactly once, when its in-degree reaches 0, so order gains one vertex per pop. For a DAG it ends with all V vertices.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> topoSort(int V, vector<vector<int>>& edges) {
        vector<vector<int>> adj(V);
        vector<int> indeg(V, 0);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);   // edge u -> v
            indeg[e[1]]++;               // v has one more parent
        }

        // Nodes with no parents can go first.
        queue<int> q;
        for (int v = 0; v < V; v++)
            if (indeg[v] == 0) q.push(v);

        vector<int> order;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);
            // u is placed, so its edges are gone. A child whose last parent was u is free now.
            for (int v : adj[u])
                if (--indeg[v] == 0) q.push(v);
        }
        // Shorter than V only when there is a cycle (not possible for a DAG).
        return order;
    }
};

import java.util.*;

class Solution {
    public int[] topoSort(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        int[] indeg = new int[V];
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);   // edge u -> v
            indeg[e[1]]++;             // v has one more parent
        }

        // Nodes with no parents can go first.
        Queue<Integer> q = new ArrayDeque<>();
        for (int v = 0; v < V; v++) {
            if (indeg[v] == 0) q.offer(v);
        }

        int[] order = new int[V];
        int idx = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            order[idx++] = u;
            // u is placed, so its edges are gone. A child whose last parent was u is free now.
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        // Shorter than V only when there is a cycle (not possible for a DAG).
        return (idx == V) ? order : Arrays.copyOf(order, idx);
    }
}

from typing import List
from collections import deque

class Solution:
    def topoSort(self, V: int, edges: List[List[int]]) -> List[int]:
        adj: List[List[int]] = [[] for _ in range(V)]
        indeg = [0] * V
        for u, v in edges:
            adj[u].append(v)   # edge u -> v
            indeg[v] += 1      # v has one more parent

        # Nodes with no parents can go first.
        q = deque([v for v in range(V) if indeg[v] == 0])

        order: List[int] = []
        while q:
            u = q.popleft()
            order.append(u)
            # u is placed, so its edges are gone. A child whose last parent was u is free now.
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)

        # Shorter than V only when there is a cycle (not possible for a DAG).
        return order

export function topoSort(V: number, edges: number[][]): number[] {
    const adj: number[][] = Array.from({ length: V }, () => []);
    const indeg: number[] = new Array(V).fill(0);
    for (const [u, v] of edges) {
        adj[u].push(v);   // edge u -> v
        indeg[v]++;       // v has one more parent
    }

    // Nodes with no parents can go first.
    const q: number[] = [];
    for (let v = 0; v < V; v++) {
        if (indeg[v] === 0) q.push(v);
    }

    const order: number[] = [];
    let head = 0;
    while (head < q.length) {
        const u = q[head++];
        order.push(u);
        // u is placed, so its edges are gone. A child whose last parent was u is free now.
        for (const v of adj[u]) {
            indeg[v]--;
            if (indeg[v] === 0) q.push(v);
        }
    }
    // Shorter than V only when there is a cycle (not possible for a DAG).
    return order;
}

Complexity

Time O(V + E)Space O(V + E)

Each edge is read once to build the lists and once more when its start vertex is placed. Each vertex enters the queue once and leaves it once. The space holds the adjacency lists (E) plus the in-degree array and the queue (V). A DFS also works: finish the vertices in post-order and reverse the list. That is O(V + E) too, but it needs recursion, so Kahn's queue is the one to learn first.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Each round, recount in-degrees and place the first free vertex	O(V · (V + E))	O(V)
Optimal	Queue every in-degree 0 vertex; placing one lowers its children's in-degree	O(V + E)	O(V + E)

Why does this belong to this pattern?

Clues in the problem statement

“directed graph with no cycles (DAG)”Edges have a direction and there is no loop, so some vertex must have no parents.
“every edge goes forward in the order”Each vertex must come after all its parents, so the first vertex has in-degree 0.
“any valid order is accepted”We need one order that respects every edge, not one exact answer. Kahn's queue gives one of many.

Directed edges u → v+u must come before v+in-degree 0 = nothing blocks the vertex→Topological Sort — Kahn's algorithm (BFS on in-degree 0)

This is the template for the whole Topological Sort pattern: a vertex with no remaining parents is always safe to place, and placing it frees its children. The later questions in this sub-pattern keep the queue and change what they count or return: course order adds a cycle check, Parallel Courses counts levels, Parallel Courses III adds durations. The pattern confusion to avoid is a plain traversal: DFS or BFS visit order follows the edges from a start point, not the rule parents first.

Don't make this mistake

Pattern confusion: printing a DFS or BFS visit order

✗ for (int v = 0; v < V; v++) if (!seen[v]) dfs(v); // print each vertex on its first visit

✓ Kahn's queue: start with the vertices whose in-degree is 0.

A visit order goes where the edges lead, not parents first. On V = 6, edges 5→2, 5→0, 4→0, 4→1, 2→3, 3→1, the DFS above prints 0, 1, 2, 3, 4, 5. That puts 2 before 5, but 5 → 2 is an edge, so the answer is wrong. Traversals answer "what can I reach?". Topological sort answers "what must come first?".

Queueing only the starts of edges

✗ for (auto& e : edges) if (indeg[e[0]] == 0) q.push(e[0]);

✓ for (int v = 0; v < V; v++) if (indeg[v] == 0) q.push(v);

A vertex with no edges at all is never queued. On V = 5, edges [[3,0],[1,0],[2,0]], vertex 4 has no edges, so the answer comes out as [3, 1, 2, 0]: only 4 vertices, not 5. Every vertex with in-degree 0 must be queued, including the isolated ones.

Returning the DFS finish order without reversing it

✗ DFS from every vertex, write each vertex when it finishes, and return that list as it is.

✓ Reverse the finish list before returning it.

A vertex finishes only after everything it points to has finished, so the finish list is the reverse of a topological order. On the dry-run graph, DFS from 0 to 5 finishes in [0, 1, 3, 2, 4, 5]. That has 2 before 5, which is backwards. Reversed it becomes [5, 4, 2, 3, 1, 0], which is valid. Kahn's queue needs no reversing.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Course Schedule II