Course Schedule II

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

Topological Sort using indegree

Similar problem:

Alien Dictionary - LeetCodeLeetCode

from collections import defaultdict,deque
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        res = []
        if not prerequisites:
            return list(range(numCourses))
        inorder = defaultdict(int)
        adj_list = defaultdict(list)
        for pair in prerequisites:
            course,preq = pair
            inorder[course]+=1
            adj_list[preq].append(course)
        queue = deque([val for val in range(numCourses) if val not in inorder])
        #print(queue)
        while queue:
            curr = queue.popleft()
            res.append(curr)
            for nxt in adj_list[curr]:
                inorder[nxt]-=1
                if inorder[nxt] == 0:
                    queue.append(nxt)
        if len(res) != numCourses:
            return []
        return res