Course Schedule I

from typing import List
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Build adjacency list: b -> list of courses that depend on b
        adj = [[] for _ in range(numCourses)]
        # indegree[x] = number of prerequisites for course x
        indegree = [0] * numCourses

        for a, b in prerequisites:
            adj[b].append(a)
            indegree[a] += 1

        # Queue courses that currently have no prerequisites
        q = deque()
        for c in range(numCourses):
            if indegree[c] == 0:
                q.append(c)

        taken = 0  # count processed courses

        # Remove prerequisites layer by layer
        while q:
            course = q.popleft()
            taken += 1

            # Taking 'course' reduces indegree of its dependent courses
            for nxt in adj[course]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    q.append(nxt)

        # If we processed all courses, no cycle exists
        return taken == numCourses