LeetCode 筆記 - 207. Course Schedule

在選修課程與先修限制中判斷是否有衝突。這題本質上是圖論中的「環偵測」問題。本文分享如何運用深度優先搜尋（DFS）遍歷節點，並透過路徑標記來識別是否存在循環依賴（Cycle），是學習拓撲排序與圖形走訪的重要基礎。

發佈: 2022.06.29
閱讀: 約 1 分鐘
字數: 287

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 207. Course Schedule

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

解題思維

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

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

程式碼

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

也許你也會想看看