LeetCode 筆記 - 210. Course Schedule II

題目在此 210. Course Schedule II

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

解題思維

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

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

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

所以就按照結束的順序,將課程收集起來即可

程式碼

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
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