LeetCode 筆記 - 207. Course Schedule

題目在此 207. Course Schedule

給定一系列的課程與先修課程,請判斷是否有衝突

解題思維

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

那我們可以使用 Depth First Search 來處理這個問題
搜尋方向是由課程往先修課程前進,一路上把節點放進 set 裡,一但看到先修課程已經在目前的路徑上
就表示 cycle 存在

程式碼

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 canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

node = [[] for _ in range(numCourses)]
for p in prerequisites:
node[p[0]].append(p[1])

visited = set()

def dfs(index, cycle):
if index in cycle:
# cycle detected
return False
if index in visited:
# visited before, so doesn't need dfs any more
return True

# put this course in dfs path
current_cycle = cycle + [index]

for i in node[index]:
if not dfs(i, current_cycle):
return False
# dfs is done and all course is ok!
visited.add(index)

return True

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

也許你也會想看看