Course Schedule

LeetCode 207 · View on LeetCode

Detect cycles in a directed graph using topological sort (Kahn's algorithm). If all nodes are processed, no cycle exists and courses can be completed.

from collections import deque, defaultdict

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    in_degree = [0] * num_courses
    for course, pre in prerequisites:
        graph[pre].append(course)
        in_degree[course] += 1

    queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
    processed = 0
    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return processed == num_courses

if __name__ == '__main__':
    print(can_finish(2, [[1, 0]]))          # True
    print(can_finish(2, [[1, 0], [0, 1]]))  # False (cycle)
    print(can_finish(4, [[1,0],[2,1],[3,2]]))  # True