Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given a directed acyclic graph (DAG) with n vertices labeled from 0 to n-1, find a topological ordering of the vertices. A topological ordering is a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v in the ordering.
Input:
- Number of vertices
n - List of directed edges as [from, to] pairs
Output:
- Array representing a valid topological ordering
- Empty array if the graph has a cycle (not a DAG)
Constraints:
- 1 ≤ n ≤ 10^4
- 0 ≤ edges.length ≤ min(10^4, n * (n-1))
- All edges are unique
- Graph may be disconnected
Examples:
Example 1:
Input: n = 4, edges = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [3, 2, 1, 0] or [3, 1, 2, 0]
Explanation: Both orderings satisfy the constraints
Example 2:
Input: n = 6, edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]
Output: [5, 4, 2, 3, 1, 0] or [4, 5, 2, 3, 1, 0] or [5, 2, 4, 3, 1, 0]
Example 3 (Has Cycle):
Input: n = 3, edges = [[0, 1], [1, 2], [2, 0]]
Output: []
Explanation: Graph has a cycle, no valid topological ordering exists
Solutions
Approach 1: DFS-Based Topological Sort
Use DFS with a stack to collect vertices in reverse topological order.
Algorithm:
- Build adjacency list from edges
- Use DFS to visit all vertices
- After visiting all descendants, push vertex to stack
- Pop all elements from stack for topological order
- Detect cycles during DFS
Python:
def topologicalSort(n, edges):
"""
DFS-based topological sort
Time: O(V + E)
Space: O(V)
"""
import sys
sys.setrecursionlimit(max(sys.getrecursionlimit(), n + 1000))
# Build adjacency list
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
# 0: White, 1: Gray, 2: Black
color = [0] * n
stack = []
has_cycle = False
def dfs(node):
nonlocal has_cycle
if color[node] == 1: # Gray - cycle detected
has_cycle = True
return
if color[node] == 2: # Black - already processed
return
color[node] = 1 # Mark as Gray
for neighbor in graph[node]:
dfs(neighbor)
if has_cycle:
return
color[node] = 2 # Mark as Black
stack.append(node) # Add to stack after processing all descendants
# Visit all vertices
for i in range(n):
if color[i] == 0:
dfs(i)
if has_cycle:
return []
# Reverse stack to get topological order
return stack[::-1]
def topologicalSortAll(n, edges):
"""
Find all possible topological orderings (for small graphs)
Time: O(V! * E) worst case
Space: O(V)
"""
import sys
sys.setrecursionlimit(max(sys.getrecursionlimit(), n + 1000))
graph = [[] for _ in range(n)]
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
def backtrack(path, remaining):
if not remaining:
results.append(path[:])
return
for node in list(remaining):
if in_degree[node] == 0:
# Choose node
path.append(node)
remaining.remove(node)
# Update in-degrees
for neighbor in graph[node]:
in_degree[neighbor] -= 1
# Recurse
backtrack(path, remaining)
# Backtrack
for neighbor in graph[node]:
in_degree[neighbor] += 1
remaining.add(node)
path.pop()
results = []
backtrack([], set(range(n)))
return results
Java:
import java.util.*;
class Solution {
private boolean hasCycle = false;
/**
* DFS-based topological sort
* Time: O(V + E)
* Space: O(V)
*/
public int[] topologicalSort(int n, int[][] edges) {
// Build adjacency list
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
}
// 0: White, 1: Gray, 2: Black
int[] color = new int[n];
Stack<Integer> stack = new Stack<>();
hasCycle = false;
// Visit all vertices
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
dfs(graph, i, color, stack);
if (hasCycle) {
return new int[0];
}
}
}
// Convert stack to array
int[] result = new int[n];
int index = 0;
while (!stack.isEmpty()) {
result[index++] = stack.pop();
}
return result;
}
private void dfs(List<List<Integer>> graph, int node, int[] color, Stack<Integer> stack) {
if (color[node] == 1) { // Gray - cycle detected
hasCycle = true;
return;
}
if (color[node] == 2) { // Black - already processed
return;
}
color[node] = 1; // Mark as Gray
// Explicit DFS stack of {node, index of next neighbor to visit}
Deque<int[]> work = new ArrayDeque<>();
work.push(new int[]{node, 0});
while (!work.isEmpty()) {
int[] frame = work.peek();
int current = frame[0];
List<Integer> neighbors = graph.get(current);
if (frame[1] < neighbors.size()) {
int neighbor = neighbors.get(frame[1]++);
if (color[neighbor] == 1) { // Gray - cycle detected
hasCycle = true;
return;
}
if (color[neighbor] == 0) {
color[neighbor] = 1; // Mark as Gray
work.push(new int[]{neighbor, 0});
}
// Black neighbors are already processed
} else {
work.pop();
color[current] = 2; // Mark as Black
stack.push(current);
}
}
}
/**
* Find all topological orderings
* Time: O(V! * E) worst case
* Space: O(V)
*/
public List<List<Integer>> topologicalSortAll(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
inDegree[edge[1]]++;
}
List<List<Integer>> results = new ArrayList<>();
Set<Integer> remaining = new HashSet<>();
for (int i = 0; i < n; i++) {
remaining.add(i);
}
backtrack(graph, new ArrayList<>(), remaining, inDegree, results);
return results;
}
private void backtrack(List<List<Integer>> graph, List<Integer> path,
Set<Integer> remaining, int[] inDegree, List<List<Integer>> results) {
// Explicit stack of frames instead of recursion, so a chain of 10^4 vertices
// cannot overflow the call stack. Each frame mirrors one recursive call:
// the candidates found on entry and the index of the next one to try.
Deque<List<Integer>> frames = new ArrayDeque<>();
Deque<int[]> nextIndex = new ArrayDeque<>();
boolean entering = true;
while (true) {
if (entering) {
entering = false;
if (remaining.isEmpty()) {
results.add(new ArrayList<>(path));
} else {
List<Integer> candidates = new ArrayList<>();
for (int node : remaining) {
if (inDegree[node] == 0) {
candidates.add(node);
}
}
frames.push(candidates);
nextIndex.push(new int[]{0});
}
}
if (frames.isEmpty()) {
return;
}
List<Integer> candidates = frames.peek();
int[] index = nextIndex.peek();
if (index[0] > 0) {
// Undo the candidate tried last (backtrack)
int node = candidates.get(index[0] - 1);
for (int neighbor : graph.get(node)) {
inDegree[neighbor]++;
}
remaining.add(node);
path.remove(path.size() - 1);
}
if (index[0] < candidates.size()) {
int node = candidates.get(index[0]++);
path.add(node);
remaining.remove(node);
for (int neighbor : graph.get(node)) {
inDegree[neighbor]--;
}
entering = true; // Descend, as the recursive call did
} else {
frames.pop();
nextIndex.pop();
}
}
}
}
Go:
// topologicalSort - DFS-based topological sort
// Time: O(V + E)
// Space: O(V)
func topologicalSort(n int, edges [][]int) []int {
// Build adjacency list
graph := make([][]int, n)
for _, edge := range edges {
graph[edge[0]] = append(graph[edge[0]], edge[1])
}
// 0: White, 1: Gray, 2: Black
color := make([]int, n)
stack := []int{}
hasCycle := false
var dfs func(node int)
dfs = func(node int) {
if color[node] == 1 { // Gray - cycle detected
hasCycle = true
return
}
if color[node] == 2 { // Black - already processed
return
}
color[node] = 1 // Mark as Gray
for _, neighbor := range graph[node] {
dfs(neighbor)
if hasCycle {
return
}
}
color[node] = 2 // Mark as Black
stack = append(stack, node)
}
// Visit all vertices
for i := 0; i < n; i++ {
if color[i] == 0 {
dfs(i)
if hasCycle {
return []int{}
}
}
}
// Reverse stack
result := make([]int, n)
for i := 0; i < n; i++ {
result[i] = stack[n-1-i]
}
return result
}
// topologicalSortAll - Find all topological orderings
// Time: O(V! * E) worst case
// Space: O(V)
func topologicalSortAll(n int, edges [][]int) [][]int {
graph := make([][]int, n)
inDegree := make([]int, n)
for _, edge := range edges {
graph[edge[0]] = append(graph[edge[0]], edge[1])
inDegree[edge[1]]++
}
results := [][]int{}
var backtrack func(path []int, remaining map[int]bool)
backtrack = func(path []int, remaining map[int]bool) {
if len(remaining) == 0 {
result := make([]int, len(path))
copy(result, path)
results = append(results, result)
return
}
// Snapshot the keys first: the loop deletes and re-adds entries of remaining
// (also inside the recursion), and Go leaves map iteration unspecified then
nodes := make([]int, 0, len(remaining))
for node := range remaining {
nodes = append(nodes, node)
}
for _, node := range nodes {
if inDegree[node] == 0 {
// Choose node
path = append(path, node)
delete(remaining, node)
// Update in-degrees
for _, neighbor := range graph[node] {
inDegree[neighbor]--
}
// Recurse
backtrack(path, remaining)
// Backtrack
for _, neighbor := range graph[node] {
inDegree[neighbor]++
}
remaining[node] = true
path = path[:len(path)-1]
}
}
}
remaining := make(map[int]bool)
for i := 0; i < n; i++ {
remaining[i] = true
}
backtrack([]int{}, remaining)
return results
}
JavaScript:
/**
* DFS-based topological sort
* Time: O(V + E)
* Space: O(V)
*/
function topologicalSort(n, edges) {
// Build adjacency list
const graph = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
}
// 0: White, 1: Gray, 2: Black
const color = new Array(n).fill(0);
const stack = [];
let hasCycle = false;
function dfs(node) {
if (color[node] === 1) { // Gray - cycle detected
hasCycle = true;
return;
}
if (color[node] === 2) { // Black - already processed
return;
}
color[node] = 1; // Mark as Gray
// Explicit DFS stack of [node, index of next neighbor to visit]
const work = [[node, 0]];
while (work.length > 0) {
const frame = work[work.length - 1];
const current = frame[0];
if (frame[1] < graph[current].length) {
const neighbor = graph[current][frame[1]++];
if (color[neighbor] === 1) { // Gray - cycle detected
hasCycle = true;
return;
}
if (color[neighbor] === 0) {
color[neighbor] = 1; // Mark as Gray
work.push([neighbor, 0]);
}
// Black neighbors are already processed
} else {
work.pop();
color[current] = 2; // Mark as Black
stack.push(current);
}
}
}
// Visit all vertices
for (let i = 0; i < n; i++) {
if (color[i] === 0) {
dfs(i);
if (hasCycle) {
return [];
}
}
}
// Reverse stack
return stack.reverse();
}
/**
* Find all topological orderings
* Time: O(V! * E) worst case
* Space: O(V)
*/
function topologicalSortAll(n, edges) {
const graph = Array(n).fill().map(() => []);
const inDegree = new Array(n).fill(0);
for (const [u, v] of edges) {
graph[u].push(v);
inDegree[v]++;
}
const results = [];
function backtrack(path, remaining) {
// Explicit stack of frames instead of recursion, so a chain of 10^4 vertices
// cannot overflow the call stack. Each frame mirrors one recursive call:
// the nodes with in-degree 0 on entry (in the same Set order as before),
// the index of the next one to try, and the node currently chosen.
const frames = [];
let entering = true;
while (true) {
if (entering) {
entering = false;
if (remaining.size === 0) {
results.push([...path]);
} else {
const candidates = [...remaining].filter(node => inDegree[node] === 0);
frames.push({ candidates, next: 0, chosen: null });
}
}
if (frames.length === 0) {
return;
}
const frame = frames[frames.length - 1];
if (frame.chosen !== null) {
// Backtrack
const node = frame.chosen;
for (const neighbor of graph[node]) {
inDegree[neighbor]++;
}
remaining.add(node);
path.pop();
frame.chosen = null;
}
if (frame.next < frame.candidates.length) {
// Choose node
const node = frame.candidates[frame.next++];
path.push(node);
remaining.delete(node);
// Update in-degrees
for (const neighbor of graph[node]) {
inDegree[neighbor]--;
}
frame.chosen = node;
entering = true; // Recurse
} else {
frames.pop();
}
}
}
const remaining = new Set();
for (let i = 0; i < n; i++) {
remaining.add(i);
}
backtrack([], remaining);
return results;
}
C#:
using System;
using System.Collections.Generic;
public class Solution {
private bool hasCycle = false;
/// <summary>
/// DFS-based topological sort
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
public int[] TopologicalSort(int n, int[][] edges) {
// Build adjacency list
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
}
// 0: White, 1: Gray, 2: Black
int[] color = new int[n];
Stack<int> stack = new Stack<int>();
hasCycle = false;
// Visit all vertices
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
Dfs(graph, i, color, stack);
if (hasCycle) {
return new int[0];
}
}
}
// Convert stack to array
int[] result = new int[n];
int index = 0;
while (stack.Count > 0) {
result[index++] = stack.Pop();
}
return result;
}
private void Dfs(List<int>[] graph, int node, int[] color, Stack<int> stack) {
// Explicit stack instead of recursion: (vertex, next neighbor index),
// where index -1 means the vertex is being entered
Stack<(int vertex, int next)> work = new Stack<(int vertex, int next)>();
work.Push((node, -1));
while (work.Count > 0) {
var (u, i) = work.Pop();
if (i == -1) {
if (color[u] == 1) { // Gray - cycle detected
hasCycle = true;
return;
}
if (color[u] == 2) { // Black - already processed
continue;
}
color[u] = 1; // Mark as Gray
work.Push((u, 0));
} else if (i < graph[u].Count) {
work.Push((u, i + 1));
work.Push((graph[u][i], -1));
} else {
color[u] = 2; // Mark as Black
stack.Push(u);
}
}
}
/// <summary>
/// Find all topological orderings
/// Time: O(V! * E) worst case
/// Space: O(V)
/// </summary>
public List<List<int>> TopologicalSortAll(int n, int[][] edges) {
List<int>[] graph = new List<int>[n];
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
inDegree[edge[1]]++;
}
List<List<int>> results = new List<List<int>>();
HashSet<int> remaining = new HashSet<int>();
for (int i = 0; i < n; i++) {
remaining.Add(i);
}
Backtrack(graph, new List<int>(), remaining, inDegree, results);
return results;
}
private void Backtrack(List<int>[] graph, List<int> path, HashSet<int> remaining,
int[] inDegree, List<List<int>> results) {
// Explicit stack of frames instead of recursion: each frame holds the candidates
// of one level and the index of the next candidate to try
List<List<int>> candidateStack = new List<List<int>>();
List<int> nextStack = new List<int>();
bool entering = true;
while (true) {
if (entering) {
entering = false;
if (remaining.Count == 0) {
results.Add(new List<int>(path));
} else {
List<int> candidates = new List<int>();
foreach (int node in remaining) {
if (inDegree[node] == 0) {
candidates.Add(node);
}
}
candidateStack.Add(candidates);
nextStack.Add(0);
}
}
if (candidateStack.Count == 0) break;
int top = candidateStack.Count - 1;
List<int> level = candidateStack[top];
int i = nextStack[top];
// Undo the candidate whose subtree just finished
if (i > 0) {
int prev = level[i - 1];
foreach (int neighbor in graph[prev]) {
inDegree[neighbor]++;
}
remaining.Add(prev);
path.RemoveAt(path.Count - 1);
}
if (i < level.Count) {
int node = level[i];
path.Add(node);
remaining.Remove(node);
foreach (int neighbor in graph[node]) {
inDegree[neighbor]--;
}
nextStack[top] = i + 1;
entering = true;
} else {
candidateStack.RemoveAt(top);
nextStack.RemoveAt(top);
}
}
}
}
Approach 2: Kahn’s Algorithm (BFS-Based)
Use BFS with in-degree tracking to find topological ordering.
Python:
from collections import deque
def topologicalSortKahn(n, edges):
"""
Kahn's algorithm for topological sort
Time: O(V + E)
Space: O(V)
"""
graph = [[] for _ in range(n)]
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
# Start with vertices having no incoming edges
queue = deque([i for i in range(n) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
# Remove this vertex from graph by reducing in-degrees
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# If all vertices are included, we have a valid topological sort
return result if len(result) == n else []
Java:
public int[] topologicalSortKahn(int n, int[][] edges) {
/**
* Kahn's algorithm for topological sort
* Time: O(V + E)
* Space: O(V)
*/
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
inDegree[edge[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int[] result = new int[n];
int index = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
result[index++] = node;
for (int neighbor : graph.get(node)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
return index == n ? result : new int[0];
}
Go:
// topologicalSortKahn - Kahn's algorithm for topological sort
// Time: O(V + E)
// Space: O(V)
func topologicalSortKahn(n int, edges [][]int) []int {
graph := make([][]int, n)
inDegree := make([]int, n)
for _, edge := range edges {
graph[edge[0]] = append(graph[edge[0]], edge[1])
inDegree[edge[1]]++
}
queue := []int{}
for i := 0; i < n; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
result := []int{}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
result = append(result, node)
for _, neighbor := range graph[node] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
if len(result) == n {
return result
}
return []int{}
}
JavaScript:
/**
* Kahn's algorithm for topological sort
* Time: O(V + E)
* Space: O(V)
*/
function topologicalSortKahn(n, edges) {
const graph = Array(n).fill().map(() => []);
const inDegree = new Array(n).fill(0);
for (const [u, v] of edges) {
graph[u].push(v);
inDegree[v]++;
}
const queue = [];
for (let i = 0; i < n; i++) {
if (inDegree[i] === 0) {
queue.push(i);
}
}
const result = [];
while (queue.length > 0) {
const node = queue.shift();
result.push(node);
for (const neighbor of graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
return result.length === n ? result : [];
}
C#:
public int[] TopologicalSortKahn(int n, int[][] edges) {
/// <summary>
/// Kahn's algorithm for topological sort
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
List<int>[] graph = new List<int>[n];
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
inDegree[edge[1]]++;
}
Queue<int> queue = new Queue<int>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
queue.Enqueue(i);
}
}
int[] result = new int[n];
int index = 0;
while (queue.Count > 0) {
int node = queue.Dequeue();
result[index++] = node;
foreach (int neighbor in graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.Enqueue(neighbor);
}
}
}
return index == n ? result : new int[0];
}
Key Insights
- DAG Requirement: Topological sort only exists for directed acyclic graphs
- Multiple Valid Orders: Many valid topological orderings may exist
- DFS vs BFS: DFS uses recursion stack, BFS uses in-degree queue
- Cycle Detection: Both approaches naturally detect cycles
Edge Cases
- Empty graph: Return vertices in any order
- No edges: Any permutation is valid
- Cycle present: Return empty array
- Disconnected graph: Process all components
- Self-loop: Immediate cycle detection
Common Mistakes
- Forgetting cycle detection: Not handling graphs with cycles
- Wrong order in DFS: Adding to result before processing descendants
- In-degree initialization: Missing edges when building graph
- Not handling disconnected components: Missing isolated vertices
Follow-up Questions
- Lexicographically smallest: Find the lexicographically smallest topological order
- Count all orderings: How many valid topological orderings exist?
- Parallel scheduling: Maximum number of vertices that can be processed in parallel
- Critical path: Find the longest path in the DAG
- Minimum edges to add: Make the graph strongly connected with minimum edges