16. Topological Sort

What you'll learn

• 1Implement Kahn's algorithm (BFS-based)
• 2Implement DFS-based topological sort
• 3Detect cycles in a directed graph

Overview

A topological sort is an ordering of nodes in a DAG (directed acyclic graph) such that for every edge u → v, u appears before v. Used for course-scheduling, build orders, dependency resolution.

Core Concepts

1. Kahn's algorithm (BFS + in-degrees)

from collections import deque

in_degree = [0] * (n + 1)
for u in range(1, n + 1):
    for v in adj[u]:
        in_degree[v] += 1

q = deque([u for u in range(1, n + 1) if in_degree[u] == 0])
order = []
while q:
    u = q.popleft()
    order.append(u)
    for v in adj[u]:
        in_degree[v] -= 1
        if in_degree[v] == 0:
            q.append(v)

if len(order) != n:
    print('Cycle detected!')
else:
    print(*order)

2. DFS-based topological sort

visited = [False] * (n + 1)
order = []

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)
    order.append(u)   # post-order — record after all descendants

for u in range(1, n + 1):
    if not visited[u]:
        dfs(u)

order.reverse()       # post-order reversed = topological order

3. Cycle detection

Kahn: if order has fewer than N nodes, there's a cycle. DFS: track 'in-progress' nodes (gray); a back-edge to gray means cycle.

4. When to pick which

• Kahn: Lexicographically-smallest order (use a min-heap instead of deque).
• DFS: Slightly less code; needs recursion limit bumped for deep DAGs.

Examples

Example 1 — src/01_kahn.py

Kahn's algorithm — BOJ 2252 (Line up by height).

Example 2 — src/02_dfs_topo.py

DFS-based topological sort with post-order.

Example 3 — src/03_lex_smallest.py

Lexicographically smallest topological order using heapq instead of deque.

Example 4 — src/04_cycle_detect.py

Detect a cycle in a directed graph.

Common Mistakes

1. Running topological sort on an undirected graph — undefined.
2. Forgetting to check cycle (order length < N) — your output might be partial.
3. Updating in-degrees in the wrong direction.
4. Using DFS on a graph with cycles → infinite loop without proper 'in-progress' marking.

Recap

• Topological sort requires a DAG.
• Kahn: BFS on in-degrees, easy cycle detection.
• DFS: post-order reversed.

Try It

1. BOJ 2252 (Line up by height).
2. BOJ 1766 (Problem solving order).