Topological sort

Tasks have prerequisites written as "a>b" (a must come before b). Find an order that respects all of them.

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

from collections import deque
def topo_order(n, edges):
    adj = [[] for _ in range(n)]; indeg = [0] * n
    for u, v in edges: adj[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 adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else []   # [] means a cycle