Topological Sort

from collections import defaultdict, deque

# ===== 1) Kahn algorithm (BFS) =====
# Build an in-degree count, repeatedly pop nodes with in_degree 0.
def topo_kahn(graph: dict):
    in_deg = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_deg[v] += 1
    # Include every node, even ones with no inbound edges
    for u in graph:
        in_deg.setdefault(u, 0)

    q = deque([n for n, d in in_deg.items() if d == 0])
    order = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)

    if len(order) != len(in_deg):
        raise ValueError('cycle detected')
    return order

# ===== 2) DFS topological sort =====
def topo_dfs(graph: dict):
    visited = {}
    order = []

    def visit(u):
        if visited.get(u) == 'gray':
            raise ValueError(f'cycle detected through {u}')
        if visited.get(u) == 'black':
            return
        visited[u] = 'gray'
        for v in graph[u]:
            visit(v)
        visited[u] = 'black'
        order.append(u)

    for u in graph:
        if visited.get(u) != 'black':
            visit(u)

    order.reverse()
    return order

# ===== Example: build system tasks =====
deps = {
    'compile':   ['link'],
    'link':      ['package'],
    'package':   ['publish'],
    'tests':     ['publish'],
    'lint':      ['package'],
    'docs':      ['publish'],
    'publish':   [],
}

print('Kahn:', topo_kahn(deps))
print('DFS:',  topo_dfs(deps))

# ===== Cycle detection — the same code, with a different report =====
broken = { 'a': ['b'], 'b': ['c'], 'c': ['a'] }
try:
    topo_kahn(broken)
except ValueError as e:
    print(e)   # cycle detected

# ===== When to pick which =====
# Kahn (BFS):
#   - Easier to parallelise (every level can run concurrently)
#   - Natural for 'how many levels' / 'longest path' problems
#   - Produces a stable order with a sorted tie-breaker
#
# DFS:
#   - Easier to write recursively
#   - Naturally produces ONE order (last-finished first)
#   - Useful when you also want to find strongly-connected components
#     after detecting a cycle

# ===== Real-world uses =====
# - Build tools (Make, Bazel, Gradle): which tasks must run before which?
# - Spreadsheets: cell A depends on cells B, C — recalc in topo order
# - Course planner: prerequisites form a DAG; the order is a valid schedule
# - Package managers: install dependencies before dependents
# - CI / CD pipelines: stage ordering across many jobs

# ===== Cap the input =====
# A DAG with N nodes and E edges sorts in O(N + E). Both algorithms are
# memory-bounded by the in-degree counter. There is no reason to write a
# different algorithm 'because the DAG is big' — write either and benchmark.

function topoSort(graph) {
    const indeg = new Map();
    for (const u of graph.keys()) indeg.set(u, 0);
    for (const vs of graph.values()) for (const v of vs) indeg.set(v, (indeg.get(v) ?? 0) + 1);
    const q = [...indeg.entries()].filter(([_, d]) => d === 0).map(([u]) => u);
    const out = [];
    while (q.length) {
        const u = q.shift(); out.push(u);
        for (const v of graph.get(u) ?? []) {
            indeg.set(v, indeg.get(v) - 1);
            if (indeg.get(v) === 0) q.push(v);
        }
    }
    return out;
}