LeetCode 筆記 - 210. Course Schedule II

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        
        node = {i:[] for i in range(numCourses)}
        for p in prerequisites:
            node[p[0]].append(p[1])
        
        visited = collections.OrderedDict()
        cycle = set()
        def dfs(index):
            if index in cycle:
                # in dfs path
                return False
            if index in visited.keys():
                # visited before, so doesn't need dfs any more
                # print(index)
                return True
            
            # put this course in dfs
            cycle.add(index)
            for i in node[index]:
                if not dfs(i):
                    return False
            cycle.remove(index)
            # dfs is done and all course is ok!
            visited.update({index:0})
            return True
        
        for i in range(numCourses):
            if not dfs(i):
                return []
        return visited