Topological Sort

1
from collections import deque
2

3
def topo(nodes, adj):
4
    indeg = {n:0 for n in nodes}
5
    for u in adj:
6
        for v in adj[u]: indeg[v]+=1
7
    q = deque([n for n in nodes if indeg[n]==0])
8
    order = []
9
    while q:
10
        u = q.popleft(); order.append(u)
11
        for v in adj.get(u,[]):
12
            indeg[v]-=1
13
            if indeg[v]==0: q.append(v)
14
    return order if len(order)==len(nodes) else None  # None => cycle