Ordering tasks so that every prerequisite is finished before its dependent task begins.
A Directed Acyclic Graph (DAG) represents dependencies (e.g., Course A must be taken before Course B). A Topological Sort gives us a valid linear order to complete all tasks.
Kahn's Algorithm works by counting the "in-degree" (number of prerequisites) for each node. Any node with 0 in-degree is ready to go! We process it, remove its outgoing edges (reducing the in-degree of its neighbors), and repeat until everything is processed.
from collections import deque
def topo_sort(num_nodes, edges):
indegree = {i: 0 for i in range(num_nodes)}
adj = {i: [] for i in range(num_nodes)}
for src, dst in edges:
adj[src].append(dst)
indegree[dst] += 1
q = deque([n for n in indegree if indegree[n] == 0])
res = []
while q:
curr = q.popleft()
res.append(curr)
for neighbor in adj[curr]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
q.append(neighbor)
return res if len(res) == num_nodes else [] # Empty if cycle exists