How to Topologically Sort a DAG in Python

from collections import defaultdict, deque


def topological_order(dependencies):
    graph = defaultdict(list)
    in_degree = defaultdict(int)
    tasks = set(dependencies.keys())

    for task, depends_on in dependencies.items():
        for d in depends_on:
            graph[d].append(task)
            in_degree[task] += 1
            tasks.add(d)

    queue = deque([t for t in tasks if in_degree[t] == 0])
    order = []

    while queue:
        current = queue.popleft()
        order.append(current)
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(tasks):
        raise ValueError("Cycle detected in dependencies")

    return order


if __name__ == "__main__":
    deps = {
        "build": ["compile", "test"],
        "compile": ["parse"],
        "test": ["compile"],
        "deploy": ["build"],
        "parse": [],
    }
    print(topological_order(deps))