course_schedule

 1from collections import defaultdict, deque
 2
 3
 4# @leet start
 5class Solution:
 6    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
 7        """
 8        This question asks us to find if we can finish all the courses provided,
 9        where each course may have any number of prerequisites.
10
11        To do this, we can do a topological sort, where we first start off by
12        taking all the courses with no prerequisites. While we're doing that,
13        we find all courses that the current course is a prerequisite to, and
14        remove it from that course. If we've taken a course that is the last
15        prerequisite for a given course, we can add that course to our queue
16        and take that course as well.
17
18        If we can follow this pattern and take all the classes, then the schedule
19        is completeable. If not, then it isn't completeable, either because
20        you can't take a given prerequisite (A requires B, but B is not a course
21        that can be completed) or there's a cycle (A requires B and B requires A),
22        which isn't completable.
23        """
24        indegrees = defaultdict(set)
25        outdegrees = defaultdict(set)
26
27        for course, prereq in prerequisites:
28            indegrees[prereq].add(course)
29            outdegrees[course].add(prereq)
30
31        q = deque([course for course in range(numCourses) if not indegrees[course]])
32
33        courses_taken = 0
34        while q:
35            course = q.popleft()
36            courses_taken += 1
37
38            for outdegree in outdegrees[course]:
39                indegrees[outdegree].remove(course)
40                if not indegrees[outdegree]:
41                    q.append(outdegree)
42
43        return courses_taken == numCourses
44
45
46# @leet end
47
48
49def test():
50    assert 2 + 2 == 4