Topological Sort — How the Pattern Works
Topological Sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u precedes vertex v. Kahn's algorithm maintains the invariant that indeg[v] tracks the exact count of unresolved prerequisites of v, dequeuing only vertices with indeg[v] == 0 whose dependencies have all been satisfied. Because each vertex enters and exits the ready queue at most once and each directed edge is relaxed once, it reduces O(V! * E) permutation testing and O(V(V + E)) repeated traversals to O(V + E) time for dependency ordering, cycle detection, and DAG dynamic programming.
- The input specifies pairwise precedence constraints (prerequisites, build dependencies, recipes and ingredients, or row/column ordering rules) and asks for a valid execution order or feasibility check.
- A hidden partial or total ordering must be inferred from sorted sequential data (such as adjacent words in an alien dictionary) or decomposed across hierarchy levels (groups and intra-group items).
- Tasks with dependencies can execute concurrently and the prompt asks for the minimum number of parallel rounds/semesters (BFS layers) or earliest completion time (critical-path DP).
- A tree problem aggregates child states into parents or shrinks an unrooted tree inward by iteratively peeling leaf nodes (degree <= 1 or children == 0).
- Reversing directed edge orientation when reading input pairs: [course, pre] means pre -> course (indeg[course] += 1), whereas [prev, next] means prev -> next (indeg[next] += 1).
- Omitting the cycle check on completion: Kahn's loop exits cleanly when cycles trap remaining nodes at indeg > 0, so always verify len(order) == V (or taken == V) before returning.
- Ignoring prefix violations or extracting multiple edges per word pair in Alien Dictionary: ["abc", "ab"] is invalid despite having no differing characters, and characters past the first mismatch carry no ordering rule.
- Mutating the current frontier mid-layer during level-by-level or leaf-peeling passes: snapshot each round's frontier before removing edges, and check len(adj[v]) > 0 when peeling the final edge between two leaves.
def kahn_topo_sort(n: int, edges: list[tuple[int, int]]) -> list[int]:
graph, indeg = [[] for _ in range(n)], [0] * n
for u, v in edges:
graph[u].append(v)
indeg[v] += 1
order = [u for u in range(n) if indeg[u] == 0]
for u in order:
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
order.append(v)
return order if len(order) == n else []def min_parallel_rounds(n: int, edges: list[tuple[int, int]]) -> int:
graph, indeg = [[] for _ in range(n)], [0] * n
for u, v in edges: graph[u].append(v); indeg[v] += 1
layer, rounds, taken = [u for u in range(n) if indeg[u] == 0], 0, 0
while layer:
rounds, taken, nxt = rounds + 1, taken + len(layer), []
for u in layer:
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0: nxt.append(v)
layer = nxt
return rounds if taken == n else -1def dag_critical_path(n: int, edges: list[tuple[int, int]], cost: list[int]) -> int:
graph, indeg = [[] for _ in range(n)], [0] * n
for u, v in edges:
graph[u].append(v); indeg[v] += 1
end, order = cost[:], [u for u in range(n) if indeg[u] == 0]
for u in order:
for v in graph[u]:
end[v] = max(end[v], end[u] + cost[v])
indeg[v] -= 1
if indeg[v] == 0: order.append(v)
return max(end, default=0)