Topological Sort

Topic type: Algorithm Paradigm LeetCode problems: ~60–80

---

Core Concepts

Topological order — a linear ordering of vertices of a directed acyclic graph (DAG) such that for every directed edge (u → v), u appears before v in the ordering. Not unique when multiple vertices have zero in-degree simultaneously.

DAG (Directed Acyclic Graph) — the necessary precondition; topological sort is undefined on graphs with cycles. A cycle means there is no valid ordering because some vertex would need to precede itself.

In-degree — number of directed edges pointing into a vertex. A vertex with in-degree 0 has no prerequisites and is always safe to process first. Kahn's algorithm is built around tracking this.

Post-order DFS — the DFS-based approach: a vertex is appended to the result only after all vertices reachable from it have been fully processed. Reversed, this yields a valid topological order.

Cycle detection via topological sort — if the topological order produced contains fewer than V vertices, a cycle exists and consumed some vertices that never reached in-degree 0 (Kahn's), or were trapped in a grey state (DFS).

Dependency graph — the modelling step common to nearly all topological sort problems: translate "A must come before B" constraints into directed edges A → B, then run topological sort on the resulting DAG.

See graph-theory.md for full graph fundamentals (DAG, adjacency list, in-degree, directed vs. undirected). See depth-first-search.md for the DFS colouring (white/grey/black) used in the DFS-based variant.

---

Types / Variants

---

Key Algorithms

Kahn's Algorithm (BFS-based)

Produces a topological order by repeatedly removing vertices with in-degree 0. Simultaneously detects cycles. Time: O(V + E), Space: O(V + E).

Key insight: a vertex with in-degree 0 has all its prerequisites satisfied — it is always valid to process it next. Removing it decrements in-degrees of its successors; any that reach 0 become newly available.

from collections import deque
queue = deque(v for v in range(V) if indegree[v] == 0)
while queue:
    u = queue.popleft(); order.append(u)
    for v in adj[u]:
        indegree[v] -= 1
        if indegree[v] == 0: queue.append(v)

Cycle check: if len(order) < V: cycle exists.

Replace deque with heapq to get the lexicographically smallest valid topological order.

DFS Post-Order (Recursive)

Runs DFS; appends each vertex to a stack after all vertices reachable from it finish. Reverse the stack for topological order. Time: O(V + E), Space: O(V) call stack.

Key insight: a vertex can only be placed in the order once everything it points to has been placed. Post-order DFS ensures this naturally.

# color: 0=white, 1=grey, 2=black
def dfs(u):
    color[u] = 1
    for v in adj[u]:
        if color[v] == 1: raise CycleError
        if color[v] == 0: dfs(v)
    color[u] = 2; result.append(u)
# result reversed is the topological order

Cycle detected when a grey vertex is reached (back edge).

Layer-by-Layer (Parallel) Kahn's

Processes all in-degree-0 vertices together in one round, then the next wave, etc. Computes the minimum number of sequential rounds (critical path length). Time: O(V + E).

Key insight: vertices in the same layer have no dependencies between them and can run in parallel. The number of layers equals the longest chain of dependencies.

layer = [v for v in range(V) if indegree[v] == 0]
rounds = 0
while layer:
    next_layer = []
    for u in layer:
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0: next_layer.append(v)
    layer = next_layer; rounds += 1

---

Advanced Techniques

DP on DAG (Topological Order DP)

Solves: Longest/shortest path in a DAG, number of paths from source to target, minimum cost to complete all tasks, counting valid orderings with constraints.

Mechanism: Process vertices in topological order (computed once). For each vertex u, update dp[v] for all successors v using dp[u]. Because u is processed before v in topological order, dp[u] is finalized when dp[v] is computed.

When to prefer over general DP: The state transitions are sparse and defined by the DAG edges — not a regular 2D grid or array recurrence. Topological DP avoids recomputing subproblems and respects dependency direction. Do not use when the graph has cycles (memoised DFS would diverge; use Bellman-Ford instead).

Complexity: O(V + E) per DP sweep after one-time O(V + E) topological sort.

for u in topo_order:
    for v, w in adj[u]:
        dp[v] = max(dp[v], dp[u] + w)

Multi-Source Topological Sort

Solves: Problems where multiple "roots" (source nodes with no predecessors) exist and you need to process the graph starting from all of them simultaneously — e.g., "remove all leaves repeatedly", "find all nodes that can never be reached from a cycle".

Mechanism: Seed the queue with all in-degree-0 vertices at once. Standard Kahn's from there. This is the same as Kahn's but the insight matters: the initial multi-source seed makes it correct even when sources form disconnected components.

When to prefer over single-source DFS: When the graph is not guaranteed to have a single entry point, or when the problem's structure is naturally "waves from all leaves/sources". Using a single DFS start point would miss disconnected components.

Complexity: O(V + E).

Topological Sort on Implicit DAGs

Solves: Problems where the graph is not given explicitly but must be constructed from constraints (character ordering, prerequisite chains inferred from comparisons, build order from file dependencies).

Mechanism: (1) Build the adjacency list and in-degree array from the constraint extraction step. (2) Run standard Kahn's. The modelling step is often the harder part.

When to use over straightforward Kahn's: Any time the DAG must be derived — alien dictionary, sequence reconstruction, course schedule with indirect constraints. Fail early if the constructed graph has contradictions (e.g., both A→B and B→A constraints → cycle).

Complexity: O(V + E) for the sort; constraint extraction varies by problem.

Detecting Unique Topological Order

Solves: "Is there exactly one valid ordering?" (e.g., Sequence Reconstruction).

Mechanism: Run Kahn's with a queue. If at any point the queue has more than one vertex, the ordering is not unique (two vertices are interchangeable at that step). Unique order exists iff the queue size is always exactly 1.

When to use over blind sort: Only when the problem explicitly asks for uniqueness. Standard Kahn's with a queue does not distinguish unique from non-unique orderings.

Complexity: O(V + E).

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Cycle in input — silent failure — Kahn's produces a partial order without error. If the caller uses order without checking its length, it silently processes fewer nodes than expected. Always assert len(order) == V after Kahn's.

• Disconnected DAG — Kahn's handles this correctly because all disconnected source vertices are added to the initial queue. DFS post-order must loop over all unvisited vertices, not start from a single source.

• Implicit DAG construction — contradictory constraints — When building the adjacency list from pairwise comparisons (e.g., alien dictionary), contradictory pairs (A→B and B→A) create a cycle. The cycle is caught by the standard len(order) < V check, but the input construction must not silently skip contradictory pairs.

• Self-loops — a vertex with a self-loop (u → u) will never reach in-degree 0 in Kahn's and will be absent from the result. This is correctly detected as a cycle. Ensure self-loops are not accidentally added during graph construction (e.g., two adjacent identical characters in alien dictionary problems).

• In-degree initialisation for isolated vertices — every vertex (including those with no incoming or outgoing edges) must appear in the in-degree array. Missing isolated vertices causes them to never enter the queue and be absent from the output, incorrectly signalling a cycle.

• Modifying in-degree of the original array — Kahn's destructively modifies in-degree values. If the graph needs to be used again (e.g., multiple test cases, or verifying uniqueness in a second pass), work on a copy.

• DFS-based — not restoring colour on backtrack — the grey/black colouring for cycle detection does not require backtracking the colour from grey back to white; once a vertex is processed (black), it never reverts. Restoring grey→white is a mistake that causes the DFS to re-enter already-completed subtrees and miss cross-edge traversals.

• Confusing DFS topo sort direction — DFS post-order must be reversed to get the correct order (vertex with no dependents is appended last, but should appear last in the ordering). Forgetting the reversal produces a valid reverse topological order, which is correct for "process dependents before dependencies" but wrong for the standard "process prerequisites first" interpretation.

• Lexicographic order requires a heap — using a plain deque in Kahn's produces a valid but arbitrary topological order. If the problem requires the lexicographically smallest valid ordering, the deque must be replaced with a min-heap; the deque approach is non-deterministic with respect to ordering.

---

Implementation Notes

• Python's collections.deque gives O(1) popleft for Kahn's BFS; a plain list's pop(0) is O(n) and causes TLE on large inputs.
• heapq in Python is a min-heap only; for lexicographically smallest topological order, push vertex labels directly (integers or strings sort naturally).
• Python's default recursion limit is 1000; DFS-based topological sort on a chain of 10^5 nodes will raise RecursionError. Use iterative DFS with explicit stack or sys.setrecursionlimit.
• defaultdict(list) is the standard adjacency list; defaultdict(int) for in-degree is convenient but indegree[v] silently creates a 0 entry on first access — this is safe for Kahn's since 0 is the correct initial value for unseen vertices.
• When constructing the implicit DAG for problems like "alien dictionary", iterate adjacent pairs in each word and stop at the first differing character — all subsequent characters in those words provide no new ordering constraint.
• For the iterative DFS post-order pattern, use stack = [(node, False)]; when popped with done=True, append to result. This mirrors the recursive version without risking stack overflow.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Ordering / Scheduling

• Course Schedule (LC 207) — detect cycle in directed graph via Kahn's
• Course Schedule II (LC 210) — return the topological order; classic Kahn's
• Course Schedule IV (LC 1462) — transitive reachability queries on DAG after topo sort

Implicit DAG Construction

• Alien Dictionary (LC 269) — derive character ordering from sorted word list; Kahn's on constructed DAG
• Sequence Reconstruction (LC 444) — verify a sequence is the unique topological order
• Sort Items by Groups Respecting Dependencies (LC 1203) — two-level topological sort (inter-group and intra-group)

Parallel Scheduling / Minimum Rounds

• Parallel Courses (LC 1136) — minimum semesters; layer-by-layer Kahn's
• Parallel Courses III (LC 2050) — minimum time with task durations; topo DP with dp[v] = max(dp[u] + time[v])
• Task Scheduler (LC 621) — greedy + frequency analysis (related but not pure topo sort)

DAG DP

• Longest Increasing Path in a Matrix (LC 329) — implicit DAG (increasing-neighbor edges); DFS + memo = topo DP
• Minimum Height Trees (LC 310) — iterative leaf removal = reverse Kahn's
• Number of Ways to Arrive at Destination (LC 1976) — count shortest paths in DAG; topo DP

Safe Nodes / Reachability

• Find Eventual Safe States (LC 802) — nodes not on any cycle; reverse graph + Kahn's
• All Ancestors of a Node in a DAG (LC 2192) — reverse edges + BFS/DFS per node, or topo sort with ancestor propagation

Clarification Questions to Ask

• Are edges directed or undirected? (Topological sort requires directed edges; undirected graphs need a different formulation.)
• Is the graph guaranteed to be a DAG, or must cycle detection be included in the solution?
• If multiple valid orderings exist, should we return any one, the lexicographically smallest, or count all of them?
• Are vertex labels 0-indexed or 1-indexed, and is the total number of vertices given explicitly?
• For scheduling problems: do tasks have durations (affects whether layer-counting or DP is needed), or are all durations unit?
• Can there be isolated vertices (no prerequisites and no dependents)? These must still appear in the output.

Common Interview Mistakes

• Returning order from Kahn's without checking len(order) == V — silently returns a partial order when a cycle exists.
• Using deque when the problem asks for lexicographically smallest order — a deque produces an arbitrary (but valid) order; swap for a min-heap.
• Forgetting to initialise in-degree for all vertices, including those that appear only as sources (in-degree 0) or are isolated — missing vertices cause incorrect cycle detection.
• Reversing the DFS post-order result in the wrong direction — DFS appends in "finished last = least dependent" order; the reverse is the valid topological order.
• Starting DFS from a single node and missing disconnected components in the DAG — always loop over all unvisited vertices.
• Confusing layer-by-layer Kahn's with plain Kahn's — plain Kahn's counts vertices, not layers; the "number of rounds" question requires explicit layer separation.

Typical Follow-Up Escalations

• "Now return the lexicographically smallest valid order." → Replace the deque in Kahn's with a min-heap; no other changes needed.
• "How many valid topological orderings exist?" → DFS backtracking on the set of in-degree-0 vertices; exponential worst case — note this is infeasible for large inputs.
• "Now tasks have durations; what is the earliest completion time?" → Topological DP: dp[v] = max(dp[u] + duration[v]) for all predecessors u; answer is max(dp).
• "What if new dependency edges are added dynamically?" → Re-run Kahn's on the updated graph; no online algorithm for incremental topological sort without full re-computation in the general case.
• "Can you detect which specific vertices form the cycle?" → DFS with grey/black colouring; grey vertices on the stack when a back edge is found form the cycle.
• "What is the minimum number of edges to remove to make the graph a DAG?" → NP-hard in general (Minimum Feedback Arc Set); mention this rather than attempting a polynomial solution.