Medium Topological Sort Advanced Graphs
In plain English: Check if you can finish all courses given their prerequisite requirements (no circular dependencies).
Build a graph and run topological sort. If the resulting order has all n courses, no cycle exists. If fewer, a cycle blocks completion.
Prompt
Given n courses and prerequisite pairs [a, b] meaning 'take b before a', determine if all courses can be completed (detect if the dependency graph has a cycle).
Try to write it from scratch before scrolling down.
Solution
from collections import deque
def can_finish(num_courses, prerequisites):
graph = {i: [] for i in range(num_courses)}
in_deg = [0] * num_courses
for a, b in prerequisites:
graph[b].append(a)
in_deg[a] += 1
q = deque(i for i in range(num_courses) if in_deg[i] == 0)
count = 0
while q:
u = q.popleft()
count += 1
for v in graph[u]:
in_deg[v] -= 1
if in_deg[v] == 0:
q.append(v)
return count == num_courses # all courses processed = no cycle
# Test: can_finish(2, [[1,0]]) == True
# Test: can_finish(2, [[1,0],[0,1]]) == False (cycle)