Solution to Leetcode 210. Course Schedule II

soln_lc210.py

# BFS 
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        from collections import defaultdict, deque 

        graph = defaultdict(list)
        for course, prereq in prerequisites:
            graph[prereq].append(course)
        
        # calculate in-degree
        in_degrees = [0]*numCourses
        for course, prereq in prerequisites:
            in_degrees[course] += 1
        
        queue = deque()
        for course in range(0, numCourses):
            # if this course does not have any prerequisites
            if in_degrees[course] == 0:
                queue.append(course)
        
        result = []
        while queue:
            node = queue.popleft()
            result.append(node)
            for next_course in graph[node]:
                in_degrees[next_course] -= 1
                if in_degrees[next_course] == 0:
                    queue.append(next_course)
        
        return result if len(result) == numCourses else []

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        '''
        The main idea is to construct two dictionaries. 
        The first dic is called next_dic, looks like
        {
            0: [1,2], 
            1: [3],
            2: [3]
        }
        The second dic is to track the in degrees. When the in degree is 0
        it means this course does not have prerequisites
        the in_degree dic looks like:
        {
            0: 0,
            1: 1,
            2: 1,
            3: 2
        }
        we want to append courses that have in degree of 0 to our nopre

        we dynamically modify the in_degree dic using this nopre and the next_dic.
        Pop one from this nopre (which means, we have taken this course)
        and then add this to our final result
        Then for courses whose key is this taken course, we deduce their indegree by 1. if the indegree becomes 0, we add this to our nopre deque

        When there is nothing there in nopre, it means there is no courses for us 
        to take. 
        '''
        from collections import defaultdict, deque 
        next_dic = defaultdict(list)
        # require how many prerequisites
        requirements = [0]*numCourses
        
        # fill 
        for course, pre in prerequisites:
            next_dic[pre].append(course)
            requirements[course] += 1
        
        to_take = deque()
        for course in range(0, numCourses):
            if requirements[course] == 0: 
                to_take.append(course)
        
        res = []
        while to_take:
            # pop() is fine but we prefer popleft() here
            # because it is more logical and easier to understand
            node = to_take.popleft()
            res.append(node)
            for next_course in next_dic[node]:
                requirements[next_course] -= 1
                if requirements[next_course] == 0:
                    to_take.append(next_course)
        
        if len(res) == numCourses: 
            return res 
        else: return []