ZERO / HERO
Getting dressed in a valid order

Topological Sort

The analogy

Socks before shoes, shirt before jacket. Some things have no relationship at all — trousers and shirt, either order. A topological sort produces any sequence that respects every "must come before" rule. And if your rules form a loop, no valid order exists, which is itself the useful answer.

Visualizer

Peeling off in-degree zero

step 1 / 9
socksshoesshirttiejackettrousersbelt

Getting dressed. Arrows mean "must come before". Some items are unrelated — shirt and trousers, either order.in-degree 0: socks, shirt, trousers

from collections import deque, defaultdict

def topo_sort(n, edges):
    g = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:            # u must come before v
        g[u].append(v)
        indeg[v] += 1

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    if len(order) != n:
        raise ValueError("cycle — no valid order exists")
    return order

import graphlib          # stdlib since 3.9
list(graphlib.TopologicalSorter(deps).static_order())
Check yourself

Kahn's algorithm emits only 7 of 10 vertices. What does that mean?