Course Schedule

Intuition

A course can be taken once every prerequisite is done, which means it can be scheduled only when nothing still points at it. We model each edge b -> a and record how many prerequisites (indegree) each course has. Courses with indegree zero have no blockers, so we start with them. Every time we finish a course we relax its outgoing edges, decreasing the indegree of the courses that depended on it, and any course that drops to zero becomes available next. If a cycle exists, the nodes inside it never reach indegree zero, so they can never be processed. Counting how many nodes we successfully processed tells us whether the whole graph was schedulable.

Algorithm walkthrough

1. 1Create an adjacency list and an indegree array; for each pair [a, b] add an edge b -> a and increment indegree[a].
2. 2Push every course whose indegree is 0 into a queue, since these have no outstanding prerequisites.
3. 3Pop a course, count it as processed, and for each dependent course reduce its indegree by one.
4. 4Whenever a dependent's indegree becomes 0, enqueue it because all of its prerequisites are now satisfied.
5. 5After the queue empties, compare the processed count to numCourses.
6. 6Return true when every course was processed; a smaller count means a cycle blocked some courses, so return false.

Implementation

from collections import deque
from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque(i for i in range(numCourses) if indegree[i] == 0)
        processed = 0
        while queue:
            node = queue.popleft()
            processed += 1
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return processed == numCourses