Topological Sort
Order a DAG so every edge points forward; Kahn's BFS using in-degrees, or DFS post-order.
Course schedule, task ordering with dependencies, alien dictionary, build order.
Each vertex is queued once and each edge decrements an in-degree once. Space holds the graph adjacency list, the in-degree array, and the queue.
Topological sort linearizes a DAG so every directed edge goes left-to-right in the output. Two algorithms: Kahn's BFS (repeatedly emit nodes with in-degree 0, decrement neighbors' in-degrees, queue new zeros) and DFS post-order (recurse, then push to a stack; reverse the stack for the order). Both are O(V + E).
Cycle detection comes for free. In Kahn's, if you emit fewer than V nodes, the unemitted ones form a cycle. In DFS, a 'gray' node (currently on the recursion stack) reached again indicates a back edge, hence a cycle. The three-color DFS (white = unvisited, gray = on stack, black = finished) is the canonical way to do this correctly.
Beyond literal dependency ordering, the pattern shows up in any 'what's the longest chain' or 'how many ways to reach the end' question on a DAG — once topologically sorted, you can do O(V + E) DP in one pass. Alien dictionary is the trick variant: you first have to extract the edges from the input data, then topo-sort.
A topological order exists if and only if the graph is acyclic, and both Kahn's algorithm and DFS post-order detect cycles as a byproduct — making topo-sort the right tool whenever 'order with dependencies' or 'is there a cycle' appears.
- In Kahn's, forgetting to enqueue all initially-zero-in-degree nodes (you'll start with an empty queue and emit nothing).
- In DFS, using a single visited boolean instead of three-color marking, conflating 'in progress' with 'done' and missing cycles.
- Returning the DFS post-order without reversing — that's reverse topological order.
- For alien dictionary, comparing all pairs of letters instead of only the first differing letter between adjacent words; also forgetting the invalid case where a longer word precedes its prefix.
- Building the graph with duplicate edges and not de-duplicating, inflating in-degree counts and breaking Kahn's.
- Kahn's BFS: in-degree array + queue, emit zeros.
- DFS post-order: recurse all children, then push self; reverse final stack.
- Lexicographically smallest topo order: replace queue with min-heap (O((V+E) log V)).
- Longest path in DAG: topo-sort then one-pass DP.
- Alien dictionary: extract edges from word pairs, then topo-sort.
// import java.util.*;
int[] indeg = new int[n];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
indeg[e[1]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.offer(i);
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int nb : graph.get(node)) {
if (--indeg[nb] == 0) queue.offer(nb);
}
}
// if order.size() != n there is a cycleProblems using this pattern
3Easiest first · Blind 75 above NeetCode 150