LeetCode 筆記 - 210. Course Schedule II

Posted on

題目在此 210. Course Schedule II

給定一系列的課程與先修課程，請給出沒有衝突的修課順序

解題思維

如果你沒解過第一題可以先看一下 LeetCode 筆記 - 207. Course Schedule

這題本質上一樣是在判斷是否有 cycle 存在，詳見 Cycle detection

那我們可以使用 Depth First Search 來處理這個問題
搜尋方向是由課程往先修課程前進，而最頂的先修課程必定會先結束 Depth First Search

所以就按照結束的順序，將課程收集起來即可，程式碼則是跟第一題一樣，只是多了一個 result 來收集結果。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        cache = collections.defaultdict(list)

        for a, b in prerequisites:
            cache[a].append(b)

        visited = set()
        
        result = []
        def dfs(index, cycle):
            if index in cycle:
                return False

            if index in visited:
                return True
            visited.add(index)

            cycle.add(index)

            cur_prerequisites = cache[index]

            for i in cur_prerequisites:
                if not dfs(i, cycle):
                    return False
            cycle.remove(index)

            result.append(index)
            return True

        for i in range(numCourses):
            if not dfs(i, set()):
                return []

        return result

也許你也會想看看