207. Course Schedule.md

207. Course Schedule (Medium)

• take all course with 0 pre and add to the queue
• traverse all course in the queue, and delete one one prerequist for other courses
• when there is still course left in the queue but no
• use a degree array and a map for storing the graph
• class A: degree = 0 | {A, [B, C, D, E]}
• when pop A, all BCDE's degree need to be reduced.

import numpy as np
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if not(prerequisites):
            return True
        # left: number of prereqs, right: next course
        course_num_pre = np.zeros(numCourses)
        course_dict = defaultdict(lambda: [])
        course_deque = deque()
        count = 0
        for one_course in prerequisites:
            pre_course, next_course = one_course[1], one_course[0] 
            # add a pre to the next course
            course_num_pre[next_course] += 1
            course_dict[pre_course].append(next_course)
            
        # add initial values to queue when no prereq
        for i in range(numCourses):
            if course_num_pre[i] == 0:
                course_deque.append(i)
                
        while(course_deque):
            course_i = course_deque.popleft()
            count += 1
            # reduce one prereq from each of next course
            # from the dict [course1, course2]
            for next_course in (course_dict[course_i]):
                course_num_pre[next_course] -= 1
                if course_num_pre[next_course] == 0:
                    course_deque.append(next_course)

        return count == numCourses