Template: 17. TOPOLOGICAL SORT — Kahn's Algorithm (BFS)

17. TOPOLOGICAL SORT — Kahn's Algorithm (BFS)

# =============================================================================
def topological_sort(num_nodes, edges):
    """edges: list of (prerequisite, dependent) pairs."""
    from collections import deque, defaultdict

    graph = defaultdict(list)
    in_degree = [0] * num_nodes

    for pre, dep in edges:
        graph[pre].append(dep)
        in_degree[dep] += 1

    queue = deque([i for i in range(num_nodes) if in_degree[i] == 0])
    order = []

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

    if len(order) == num_nodes:
        return order  # valid topological order
    else:
        return []  # cycle detected


# =============================================================================