The machine must decide whether all courses can be finished given prerequisite pairs where [a, b] means course a requires course b. This is a cycle-detection problem in disguise: a valid schedule exists if and only if the prerequisite graph has no directed cycle, because a cycle means no course in it can ever be taken first.
The key insight is that Kahn's algorithm turns cycle detection into counting. The machine repeatedly removes courses with zero remaining prerequisites; if it can remove all courses, the graph is acyclic and a schedule exists. If removal stalls with courses left over, those leftovers are trapped in a cycle.
The approach has three steps. First, build the adjacency list from the prerequisite pairs and compute the in-degree of every course. Second, seed a queue with all zero-in-degree courses and process it, decrementing the in-degree of each dependent course and enqueueing any that reach zero. Third, count the courses processed; if the count equals numCourses, return true. Time is O(V + E) to build and walk the graph, and space is O(V + E) for the adjacency list.
The trickiest edge case is the two-course cycle [1,0] and [0,1]: both courses start with in-degree 1, the queue is empty from the start, and the count stays 0 — false. A course with no prerequisites at all must also work as a seed for the queue.
from collections import deque
def canFinish(numCourses, prerequisites):
adj = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for a, b in prerequisites:
adj[b].append(a)
indegree[a] += 1
q = deque(i for i in range(numCourses) if indegree[i] == 0)
taken = 0
while q:
course = q.popleft()
taken += 1
for nxt in adj[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return taken == numCourses