207. Course Schedule

• 思路
  • example
  • 有向圖

graph[from] = to, 先修from才能修to

• 關(guān)鍵：是否存在環(huán)

無法修完所有課程: 存在循環(huán)依賴

• 避免重復(fù)訪問節(jié)點(diǎn)：用visited數(shù)組
• 判斷當(dāng)前路徑中是否有環(huán)：用path數(shù)組 (回溯）

選擇撤銷操作在循環(huán)外
類比貪吃蛇游戲，visited 記錄蛇經(jīng)過過的格子，而 onPath 僅僅記錄蛇身。onPath 用于判斷是否成環(huán)，類比當(dāng)貪吃蛇自己咬到自己（成環(huán)）的場景。

• 復(fù)雜度. 時間：O(?), 空間: O(?)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        def traversal(graph, i):
            if onPath[i]: # 找到環(huán)
                return False 
            if visited[i]:
                return True
            visited[i] = True 
            onPath[i] = True 
            for j in graph[i]:
                if traversal(graph, j) == False:
                    return False 
            onPath[i] = False # 回溯
            return True  
        graph = collections.defaultdict(list)
        for pair in prerequisites:
            graph[pair[1]].append(pair[0]) # graph[from] = to
        visited = [False for _ in range(numCourses)]
        onPath = [False for _ in range(numCourses)] # 當(dāng)前路徑
        for i in range(numCourses):
            if traversal(graph, i) == False: # 有環(huán)
                return False 
        return True 

• 進(jìn)階：返回這個環(huán)具體有哪些節(jié)點(diǎn)

  
  

TBA

210. Course Schedule II

• 思路
  • example
  • 有向圖
  • BFS
  • 入度
• 復(fù)雜度. 時間：O(?), 空間: O(?)

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(list)
        inDeg = [0 for _ in range(numCourses)]
        for pair in prerequisites:
            graph[pair[1]].append(pair[0]) # graph[from] = to
            inDeg[pair[0]] += 1
        que = collections.deque()
        for i in range(numCourses):
            if inDeg[i] == 0:
                que.append(i)
        res = []
        while que:
            i = que.popleft() # 待加進(jìn)結(jié)果列表的課程
            res.append(i) # 必有inDeg[i] == 0
            for j in graph[i]:
                inDeg[j] -= 1
                if inDeg[j] == 0: # 課程j沒有先決課程了，可以準(zhǔn)備加進(jìn)結(jié)果列表
                    que.append(j)
        if len(res) == numCourses:
            return res 
        else:
            return []

[圖的遍歷]一般需要 visited 數(shù)組防止走回頭路，這里的 BFS 算法其實是通過 indegree 數(shù)組實現(xiàn)的 visited 數(shù)組的作用，只有入度為 0 的節(jié)點(diǎn)才能入隊，從而保證不會出現(xiàn)死循環(huán)。