演算法練習 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