Topological sort orders dependencies — Kahn's BFS algorithm detects cycles and returns valid ordering.
Topological Sort
from collections import deque
# Kahn's Algorithm (BFS-based) -- O(V+E)
def topo_sort(num_nodes, edges):
adj = [[] for _ in range(num_nodes)]
indeg = [0] * num_nodes
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
queue = deque(i for i in range(num_nodes) if indeg[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nb in adj[node]:
indeg[nb] -= 1
if indeg[nb] == 0:
queue.append(nb)
if len(order) == num_nodes:
return order # valid topological order
return [] # cycle detected
# Course Schedule (LeetCode 207)
# Can finish courses given prerequisites?
def can_finish(n, prerequisites):
order = topo_sort(n, prerequisites)
return len(order) == n # False if cycle