207. Course Schedule

Question: Course Schedule

Solution

想法：

1. 每一堂課可能會有 prerequisite，所以要做一個 course map: Course → prerequisites []
2. 如果 1: [2, 3] 就要依次去看 2, 3 的 prerequisites，如果 2:[4]，就要繼續看 4 的 prerequisites，如果 4: []，就 return ，代表 2 成功看完，繼續看 3
3. 由上述可知，做完 course map 之後，一個個 Course 去看，看的方式是 DFS(course)，如果可以成功看完就 return True，不行就 return False
4. 為了防止 loop 的情況 1:[0], 0: [1]，loop 代表課程重複 → set()，for loop 看每一個課程的時候，用 set 去記錄拜訪過的課程 visited: {1, } 這樣找到 0 的時候就可以知道 1 已經拜訪過了，return False

from collections import defaultdict

class Solution(object):

def canFinish(self, numCourses, prerequisites):

"""

:type numCourses: int

:type prerequisites: List[List[int]]

:rtype: bool

"""

# 製作 course map

pre_map = defaultdict(list)

for c, pre_c in prerequisites:

pre_map[c].append(pre_c)

# DFS(course) 給 course return T/F 這個 course 是否可以成功修完

visited = set()

def dfs(course):

if course in visited:

return False

elif course not in pre_map:

return True

# 拜訪過課程

visited.add(course)

pre_requisites = pre_map[course]

for c in pre_requisites:

if not dfs(c):

return False

# 成功拜訪完他的先修課程，把這堂課從記錄中去除

visited.remove(course)

pre_map[course] = list()

return True

# 全部課程都要看一遍，如果課程間沒關聯會漏看

# ex:{1: [2], 3:[4]} 1 跟 3 沒有關係

for k in pre_map.keys():

if not dfs(k):

return False

return True

Video Solution