Graph Exploration Target: 20s
Kahn's algorithm: start from zero in-degree nodes, peel layers. If len(order) < n, there's a cycle.
from collections import deque, defaultdict
in_deg = [0] * n
graph = defaultdict(list)
for a, b in edges:
graph[b].append(a)
in_deg[a] += 1
q = deque(i for i in range(n) if in_deg[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nb in graph[node]:
in_deg[nb] -= 1
if in_deg[nb] == 0:
q.append(nb)Type it from memory. Go.