Course Schedule

Problem

Package managers and build systems need to verify that dependency graphs are acyclic before executing a build plan. Given numCourses and a list of prerequisite pairs where [a, b] means course b must be taken before course a, determine if it is possible to finish all courses.

numCourses=2, prerequisites=[[1,0]]       → True  (take 0 then 1)
numCourses=2, prerequisites=[[1,0],[0,1]] → False (0 requires 1, 1 requires 0)
numCourses=4, prerequisites=[[1,0],[2,1],[3,2]] → True (linear chain)

Solution

Approach: Kahn's algorithm - topological sort by repeatedly peeling off in-degree-0 nodes; cycle detected by a short count.

Model each course as a node and each pair [course, prereq] as a directed edge prereq -> course, so adjacency[prereq] lists the courses that prereq unlocks, and in_degree[course] counts how many prerequisites still block it. Seed the queue with every node whose in-degree is already 0 - those depend on nothing and can be taken first. The loop pops a node, counts it as completed, and decrements the in-degree of each course it unlocks; any course that drops to in-degree 0 has all its prerequisites satisfied and joins the queue. This removal order is a valid topological order because a node is only released after every edge into it has been resolved. The cycle test is implicit: if completed == num_courses, every course was eventually freed, so no cycle. If the loop drains the queue with completed < num_courses, the leftover courses each still wait on one another - that mutual wait is the cycle, and no ordering exists. Trace [[0,1],[1,2],[2,0]]: every course has in-degree 1, the seed queue is empty, the loop never runs, completed stays 0, and the function returns False.

Edge cases: No prerequisites means every course starts at in-degree 0 and all are processed (returns True). A self-loop or any cycle leaves nodes permanently above in-degree 0, so they are never queued.

Complexity: O(V + E) time, O(V + E) space - each node is enqueued once, each edge is decremented once, and the adjacency list dominates the space.