# Title: Topological sort
# Heading: Python Program for Topological Sort (Kahn's Algorithm)
# Level: advanced
# Tags: topological sort, kahn's algorithm, dag, dependencies, in-degree
# Time: O(V + E)
# Space: O(V)
# About: Orders courses so that each comes after the courses it needs, with Kahn's algorithm: count each one's prerequisites, then use a queue.

from collections import deque


def topological_sort(graph):
    """The nodes in an order where every edge points forward."""
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for after in graph[node]:
            in_degree[after] += 1
    queue = deque(node for node in graph if in_degree[node] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for after in graph[node]:
            in_degree[after] -= 1
            if in_degree[after] == 0:  # all it needs is done
                queue.append(after)
    if len(order) < len(graph):
        return None  # a cycle: some nodes wait on each other
    return order


# Each course, and the courses that build on it
courses = {
    "Python": ["Data", "Web"],
    "Maths": ["Data"],
    "Data": ["ML"],
    "Web": ["Project"],
    "ML": ["Project"],
    "Project": [],
}
print("Course order:", topological_sort(courses))