Course Schedule

The problem

Given a set of courses and their prerequisites, determine whether it is possible to finish every course. The interesting case is a cycle: course A requires B, while B eventually requires A.

A solution

Model the prerequisites as a directed graph. Start with courses that have no remaining prerequisites. Each time a course is completed, remove its contribution to the indegree of the courses that depend on it.

from collections import deque

def can_finish(num_courses, prerequisites):
    next_courses = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, prerequisite in prerequisites:
        next_courses[prerequisite].append(course)
        indegree[course] += 1

    ready = deque(i for i, count in enumerate(indegree) if count == 0)
    completed = 0

    while ready:
        course = ready.popleft()
        completed += 1
        for dependent in next_courses[course]:
            indegree[dependent] -= 1
            if indegree[dependent] == 0:
                ready.append(dependent)

    return completed == num_courses

assert can_finish(2, [[1, 0]])
assert not can_finish(2, [[1, 0], [0, 1]])

Notes

The useful signal is dependencies, not the word “course.” The same shape appears in build systems and task scheduling.

• Time: O(V + E), visiting every course and prerequisite once.
• Space: O(V + E) for the adjacency lists, indegrees, and queue.
• A disconnected graph still works because every zero-indegree node enters the initial queue.

What to revisit

Try the depth-first search version next and compare how it reports a cycle.