Course Schedule LeetCode solution in Python

1
class Solution:
2
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3

4
        pre = {}  # course: list of prerequisites
5
        dep = {}  # course: list of dependents
6
        for p in prerequisites:
7
            if p[0] not in pre:
8
                pre[p[0]] = set()
9
            if p[1] not in dep:
10
                dep[p[1]] = set()
11
            pre[p[0]].add(p[1])
12
            dep[p[1]].add(p[0])
13

14
        # Kahn's algorithm
15
        l = []
16
        s = set()
17
        for i in range(numCourses):
18
            if i not in dep:  # if no dependents (incoming edge)
19
                s.add(i)
20
        while s:
21
            n = s.pop()
22
            l.append(n)
23
            if n in pre:  # if n has prerequisites
24
                for m in pre[n]:  # for each prerequisites m
25
                    dep[m].remove(n)  # remove n from m's dependents list
26
                    if not dep[m]:  # if m has no more dependents
27
                        s.add(m)
28

29
        return len(l) == numCourses