Q84: Course Schedule (I & II). - DSA Patterns (Multi-Lang)

In Simple Words: Topological Sort (Kahn's Algorithm):

Compute in-degree for each course.
Queue all courses with in-degree 0.
Process courses: decrement neighbors' in-degree. If neighbor hits 0, enqueue it. If count processed equals $N$, no cycle exists.

Time: $O(V + E)$ | Space: $O(V + E)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

from collections import deque

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    adj = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    for crs, pre in prerequisites:
        adj[pre].append(crs)
        in_degree[crs] += 1
    q = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0
    while q:
        curr = q.popleft()
        count += 1
        for nei in adj[curr]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                q.append(nei)
    return count == numCourses