算法练习 Leetcode 力扣 210. Course Schedule II 解法

feellikelearning June 20, 2020 0 Comments

这题基本和269 alien dictionary一样，难度为medium。其实269 alien dictionary比这题多了就是建graph的过程而这题的graph基本是已经给定的。重点还是topological sort部分。比207. Course Schedule多了两行handle sort部分。以下为同样思路的python解法，比较简短，容易写对。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        edges = {c: set() for c in range(numCourses)}
        for pr in prerequisites:
            edges[pr[1]].add(pr[0])
            
        order = []
        seen = {}
        
        def dfs(start):
            if start in seen:
                return seen[start]
            seen[start] = False
            for nxt in edges[start]:
                if not dfs(nxt):
                    return False
            seen[start] = True
            order.insert(0, start)
            return True
            
        if not all(dfs(start) for start in range(numCourses)):
            return []
        return order