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)
"""
# 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)
"""
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 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
for (int neighbor : graph.get(node)) {
dfs(graph, neighbor, color, stack);
if (hasCycle) return;
}
color[node] = 2; // Mark as Black
stack.push(node);
}
/**
* 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) {
if (remaining.isEmpty()) {
results.add(new ArrayList<>(path));
return;
}
List<Integer> candidates = new ArrayList<>();
for (int node : remaining) {
if (inDegree[node] == 0) {
candidates.add(node);
}
}
for (int node : candidates) {
path.add(node);
remaining.remove(node);
for (int neighbor : graph.get(node)) {
inDegree[neighbor]--;
}
backtrack(graph, path, remaining, inDegree, results);
for (int neighbor : graph.get(node)) {
inDegree[neighbor]++;
}
remaining.add(node);
path.remove(path.size() - 1);
}
}
}
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
}
for node := range remaining {
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
for (const neighbor of graph[node]) {
dfs(neighbor);
if (hasCycle) return;
}
color[node] = 2; // Mark as Black
stack.push(node);
}
// 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) {
if (remaining.size === 0) {
results.push([...path]);
return;
}
for (const node of remaining) {
if (inDegree[node] === 0) {
// Choose node
path.push(node);
remaining.delete(node);
// Update in-degrees
for (const neighbor of graph[node]) {
inDegree[neighbor]--;
}
// Recurse
backtrack(path, remaining);
// Backtrack
for (const neighbor of graph[node]) {
inDegree[neighbor]++;
}
remaining.add(node);
path.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) {
if (color[node] == 1) { // Gray - cycle detected
hasCycle = true;
return;
}
if (color[node] == 2) { // Black - already processed
return;
}
color[node] = 1; // Mark as Gray
foreach (int neighbor in graph[node]) {
Dfs(graph, neighbor, color, stack);
if (hasCycle) return;
}
color[node] = 2; // Mark as Black
stack.Push(node);
}
/// <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) {
if (remaining.Count == 0) {
results.Add(new List<int>(path));
return;
}
List<int> candidates = new List<int>();
foreach (int node in remaining) {
if (inDegree[node] == 0) {
candidates.Add(node);
}
}
foreach (int node in candidates) {
path.Add(node);
remaining.Remove(node);
foreach (int neighbor in graph[node]) {
inDegree[neighbor]--;
}
Backtrack(graph, path, remaining, inDegree, results);
foreach (int neighbor in graph[node]) {
inDegree[neighbor]++;
}
remaining.Add(node);
path.RemoveAt(path.Count - 1);
}
}
}
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