Topological sorting, Tarjan and Kosaraju

A topological order of a DAG places u beforev for every u→v edge. Kahn removes zero-indegree vertices; producing fewer thanV vertices proves a cycle. Orders need not be unique. Build dependencies and prerequisites are natural applications.

An SCC is a maximal set of mutually reachable vertices. Contracting SCCs forms a DAG. Kosaraju uses finishing order and then reversed finishing order on the transposed graph; arbitrary second-pass order is incorrect.

Tarjan maintains DFS indices, low links and an active stack. Edges into already completed SCCs must not incorrectly lower low links. When low[u]==index[u], pop one component. Bridge/articulation low-link rules solve different problems and should not be copied blindly.

from collections import deque

def topo(g):
    degree = {u: 0 for u in g}
    for u in g:
        for v in g[u]: degree[v] += 1
    q, out = deque(u for u in g if degree[u] == 0), []
    while q:
        u = q.popleft(); out.append(u)
        for v in g[u]:
            degree[v] -= 1
            if degree[v] == 0: q.append(v)
    if len(out) != len(g): raise ValueError("cycle")
    return out
assert topo({"A":["B"],"B":[]}) == ["A","B"]