207. Course Schedule

https://leetcode.com/problems/course-schedule/

Python

BFS

from collections import defaultdict, deque


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(set)
        ingress = [0] * numCourses

        for edge in prerequisites:
            graph[edge[1]].add(edge[0])
            ingress[edge[0]] += 1

        queue = deque()
        for course in range(numCourses):
            if ingress[course] == 0:
                queue.append(course)

        while queue:
            course = queue.popleft()
            for prereq in graph[course]:
                ingress[prereq] -= 1
                if ingress[prereq] == 0:
                    queue.append(prereq)

        return all(item == 0 for item in ingress)