Log inSign up
mediumLeetCodeNot Started

Topological Sort

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

Given a Directed Acyclic Graph (DAG) with V vertices labeled from 0 to V - 1 and E edges represented as an adjacency list adj.

A Topological Sort of a directed acyclic graph is a linear ordering of its vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.

Find and return any valid topological ordering of the vertices. If the graph contains a cycle, return an empty array.

Constraints:

  • 1 <= V <= 104
  • 0 <= E <= min(V * (V - 1) / 2, 105)
  • 0 <= u, v < V
  • The graph is directed and may contain disconnected components.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Define topological ordering and its existence condition (DAG).
  • Implement Kahn's Algorithm (BFS) with in-degree bookkeeping.
  • Implement DFS-based topological sort with stack / post-order reversal.
  • Detect cycles in directed graphs using in-degree exhaustion.
  • Analyze time and space complexity (O(V + E)).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever tasks, courses, packages, or build targets have prerequisite dependencies (u must happen before v), model them as directed edges u -> v and compute a Topological Sort.

1. Repeated Zero In-Degree Linear Search

Intuition

Compute the in-degree of all vertices. In each of the V steps, linearly scan the vertices to find an unvisited vertex with in-degree 0. Add it to the topological ordering, mark it visited, and decrement in-degrees of all its neighbors. If no such vertex can be found before all V vertices are picked, a cycle exists.

Algorithm

  1. Compute inDegree array of size V.
  2. Initialize visited array of size V with false.
  3. Initialize order = [].
  4. Loop V times:
  5. Find an unvisited vertex u with inDegree[u] == 0.
  6. If no such vertex exists, return [] (cycle detected).
  7. Mark visited[u] = true, append u to order.
  8. For each neighbor v of u, decrement inDegree[v].
  9. Return order.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4std::vector<int> topoSortBrute(int V, const std::vector<std::vector<int>>& adj) {
5 std::vector<int> inDegree(V, 0);
6 for (int u = 0; u < V; ++u) {
7 for (int v : adj[u]) {
8 inDegree[v]++;
9 }
10 }
11
12 std::vector<bool> visited(V, false);
13 std::vector<int> order;
14
15 for (int step = 0; step < V; ++step) {
16 int u = -1;
17 for (int i = 0; i < V; ++i) {
18 if (!visited[i] && inDegree[i] == 0) {
19 u = i;
20 break;
21 }
22 }
23
24 if (u == -1) return {}; // Cycle detected
25
26 visited[u] = true;
27 order.push_back(u);
28
29 for (int v : adj[u]) {
30 inDegree[v]--;
31 }
32 }
33
34 return order;
35}
36
37int main() {
38 int V = 4;
39 std::vector<std::vector<int>> adj = {{1, 2}, {3}, {3}, {}};
40 auto res = topoSortBrute(V, adj);
41 std::cout << "Topo Sort (Brute): ";
42 for (int x : res) std::cout << x << " ";
43 std::cout << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(V^2 + E) because in each of the V steps we linearly scan all V vertices to find an in-degree 0 vertex.
  • Space complexity: O(V + E) for the adjacency list and inDegree array.

2. DFS with Post-Order Reversal (3-Color State)

Intuition

Perform DFS from every unvisited node. To detect cycles, color vertices with 3 states: 0 = unvisited, 1 = visiting (on current recursion stack), 2 = visited. If DFS encounters a node with state 1, a back-edge (cycle) exists. When all descendants of node u have finished, push u to a stack. Reversing the finish order yields the topological sort.

Algorithm

  1. Initialize state array of size V with 0 (0: unvisited, 1: visiting, 2: visited).
  2. Initialize st = [].
  3. Define dfs(u):
  4. state[u] = 1
  5. For each neighbor v of u:
  6. If state[v] == 1, return false (cycle detected).
  7. If state[v] == 0:
  8. If !dfs(v), return false.
  9. state[u] = 2
  10. Push u to st.
  11. Return true.
  12. For i = 0 to V - 1:
  13. If state[i] == 0:
  14. If !dfs(i), return [].
  15. Reverse st and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5bool dfsTopo(int u, const std::vector<std::vector<int>>& adj, std::vector<int>& state, std::vector<int>& order) {
6 state[u] = 1; // visiting
7 for (int v : adj[u]) {
8 if (state[v] == 1) return false; // Cycle detected
9 if (state[v] == 0) {
10 if (!dfsTopo(v, adj, state, order)) return false;
11 }
12 }
13 state[u] = 2; // visited
14 order.push_back(u);
15 return true;
16}
17
18std::vector<int> topoSortDFS(int V, const std::vector<std::vector<int>>& adj) {
19 std::vector<int> state(V, 0);
20 std::vector<int> order;
21
22 for (int i = 0; i < V; ++i) {
23 if (state[i] == 0) {
24 if (!dfsTopo(i, adj, state, order)) return {};
25 }
26 }
27
28 std::reverse(order.begin(), order.end());
29 return order;
30}
31
32int main() {
33 int V = 4;
34 std::vector<std::vector<int>> adj = {{1, 2}, {3}, {3}, {}};
35 auto res = topoSortDFS(V, adj);
36 std::cout << "Topo Sort (DFS): ";
37 for (int x : res) std::cout << x << " ";
38 std::cout << std::endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(V + E) single DFS traversal visiting every node and edge once.
  • Space complexity: O(V + E) for the adjacency list, recursion stack, and result array.

3. Kahn's Algorithm (BFS with In-Degrees)

Intuition

Instead of searching for 0 in-degree nodes linearly in O(V), use a FIFO queue. Vertices with in-degree 0 are ready to execute immediately. When a vertex is popped from the queue, decrement the in-degree of all its outgoing neighbors. If a neighbor's in-degree drops to 0, it becomes ready and is enqueued. If all V vertices are processed, the order is complete; otherwise, a cycle exists.

Algorithm

  1. Initialize inDegree array of size V with 0.
  2. For each vertex u and outgoing edge u -> v, increment inDegree[v].
  3. Initialize queue q. Push all vertices with inDegree[i] == 0 into q.
  4. Initialize order = [].
  5. While q is not empty:
  6. Pop u = q.front().
  7. Append u to order.
  8. For each neighbor v of u:
  9. inDegree[v]--
  10. If inDegree[v] == 0, push v to q.
  11. If order.size() == V, return order; else return [] (cycle detected).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5std::vector<int> topoSort(int V, const std::vector<std::vector<int>>& adj) {
6 std::vector<int> inDegree(V, 0);
7 for (int u = 0; u < V; ++u) {
8 for (int v : adj[u]) {
9 inDegree[v]++;
10 }
11 }
12
13 std::queue<int> q;
14 for (int i = 0; i < V; ++i) {
15 if (inDegree[i] == 0) {
16 q.push(i);
17 }
18 }
19
20 std::vector<int> order;
21 while (!q.empty()) {
22 int u = q.front();
23 q.pop();
24 order.push_back(u);
25
26 for (int v : adj[u]) {
27 if (--inDegree[v] == 0) {
28 q.push(v);
29 }
30 }
31 }
32
33 if (order.size() != V) return {}; // Cycle detected
34 return order;
35}
36
37int main() {
38 int V = 4;
39 std::vector<std::vector<int>> adj = {{1, 2}, {3}, {3}, {}};
40 auto res = topoSort(V, adj);
41 std::cout << "Optimal Topo Sort (Kahn's): ";
42 for (int x : res) std::cout << x << " ";
43 std::cout << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(V + E) linear time. Each vertex is enqueued/dequeued once, each edge is traversed once.
  • Space complexity: O(V + E) for the adjacency list, inDegree array, and BFS queue.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear In-Degree ScanO(V^2 + E)O(V + E)Simple conceptual demonstration of removing 0 in-degree nodes.Scanning all V vertices on every step leads to quadratic runtime.
2.DFS with Post-Order ReversalO(V + E)O(V + E)Very clean recursive implementation; handles cycle detection with 3-color states.Requires reversing the output array and relies on call stack depth.
3.Kahn's Algorithm (BFS)OptimalO(V + E)O(V + E)Iterative queue-based; naturally detects cycles when order.length < V; produces forward order directly.Requires computing in-degrees upfront.

Common Pitfalls & Crucial Edge Cases

Forgetting to check order.length == V at the end of Kahn's algorithm.

If a cycle exists, the queue will empty before all nodes are visited; failing to check returns an incomplete order instead of indicating an error/cycle.

Forgetting to reverse the DFS post-order list.

Post-order exit finishes descendants first; the array must be reversed to put prerequisites before dependents.

Crucial Edge Cases to Validate:

  • Graph with a directed cycle (e.g. 0 -> 1 -> 0) — Kahn's algorithm queue empties with order.size() < V; returns empty array.
  • Completely disconnected graph with 0 edges — All V vertices have in-degree 0; all are enqueued, returns any permutation of 0..V-1.
  • Single vertex (V = 1) — In-degree is 0; returns [0].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Know both Kahn's algorithm (BFS) and DFS post-order reversal fluently. Explain why Kahn's makes cycle detection so trivial (count != V).
  2. Mention the real-world applications: Course Schedule, Makefile build task dependency resolution, Excel spreadsheet formula recalculation order.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Can an undirected graph have a valid topological sort?

2.How does Kahn's algorithm detect if a directed graph has a cycle?

3.Is the topological sort of a DAG always unique?

Back to DSA Sheet