210. Course Schedule II

Question: Course Schedule II

Solution

想法：

可以先做看看 207. Course Schedule 這題

1. 先做一個 Course 的 Hash map: course_to_pre，看每一堂課會對應到哪些 prerequisites
2. 一堂課能不能修，要看他的 pre 修完了沒，所以要一直往下找每一堂課的 pre -> DFS
3. 當 map 建立好之後，for loop 每一堂課程
4. 課程會分成三種狀態
1. 還沒拜訪過的，沒有加入到 visited 也沒有加入 cycle
2. 正在拜訪的，進入重複 cycle
3. 拜訪過的
5. 所以需要準備兩個 set
• visited：存放已經拜訪過的課程，也就是加入最後結果的課程，之後如果遇到，就不用再加入一次
• cycle：存放正在拜訪的過程，例如 [[1, 0], [0, 1]]，當找到課程 1，將 1 課程加入 cycle，進入課程 0，將 0 課程加入 cycle，又會回到課程 1，他已經在 cycle 裡面，代表沒辦法把課修完。

class Solution(object):

def findOrder(self, numCourses, prerequisites):

"""

:type numCourses: int

:type prerequisites: List[List[int]]

:rtype: List[int]

"""

course_pres = {i:list() for i in range(numCourses)}

for course, prerepuiste in prerequisites:

course_pres[course].append(prerepuiste)

# a course has three possible states:

# visited -> course has been added to result

# visiting -> course not in result but was added to cycle

# unvisited -> course not added to result or cycle

res = list()

visited, cycle = set(), set()

def dfs(course):

if course in cycle:

return False

elif course in visited:

return True

cycle.add(course)

for pre in course_pres[course]:

if not dfs(pre):

return False

visited.add(course)

res.append(course)

cycle.remove(course)

return True

for k in course_pres.keys():

if not dfs(k):

return []

return res

Video Solution