題目

  • 題目連結
  • 目標函式 : canFinish(numCourses, prerequisites)
    • Input : numCourses: int、prerequisites: List[List[int]]
    • Output : bool

解題概念

  • 題意 : 必須修習的課程總數為 numCourses，label 從 0 到 numCourses - 1。
    • 題目給予一陣列 prerequisites，其中先決條件 prerequisites[i] = [a_i, b_i] ，代表如果想修 a_i，就得先修 b_i
    • 如果可以完成所有課程即回傳 true，不然回傳 false

我的寫法

  • 想法 : 知道要使用 DFS 或 BFS 去處理
  • 面臨問題 : 由於 prerequisites 有先後關係存在，因此在做 DFS 或 BFS 時不知道從何下手…

解答 or 其他優秀寫法 - BFS

  • 想法 : 這題其實要用 Graph 去解決，如果將每堂課程畫成 Graph 中的節點，prerequisites[i] 視為 Edge，則此題就是 在 Directed Graph 去偵測有無 Cycle 存在 !
    • 而最經典的偵測方法就是使用 BFS 中的 Topological Sort
    • 使用變數 :
      • adjList : 使用 Adjacency List 去儲存每個節點的 Neighbors
      • inDegree : 儲存每個節點的 In-Degree edge 數量
      • queue : 供 BFS 使用的 Queue
      • cnt : 紀錄當前已處理過的累計課程數量
    • 詳細說明請見程式碼
  • 程式碼 : 
    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
    def canFinish(self, numCourses, prerequisites):
        
        # 初始化 Adjacency List 與 In-Degree
        adjList = [[] for _ in range(numCourses)]
        inDegrees = [0 for _ in range(numCourses)]
        for c1, c2 in prerequisites:
            adjList[c2].append(c1) # 代表 c2 指向 c1
            inDegrees[c1] += 1
        
        queue = []
        # 找出一開始 In-Degree 為 0 的節點，以作為 BFS 的起始點
        for v in range(numCourses):
            if inDegrees[v] == 0:
                queue.append(v)
        
        count = 0

        while queue:
            
            course = queue.pop(0)
            count += 1
            
            for des in adjList[course]: # 針對該節點的所有 neighbors
                inDegrees[des] -= 1 # 該 neighbor 的 inDegrees 數量 - 1 
                if inDegrees[des] == 0: # 若此時該 neighbor 的 inDegrees 數量歸零
                    queue.append(des) # 則將它 push 到 queue 中

        # 最後去判斷 count 是否等於 numCourses 
        # 若是，代表無 cycle 存在，反之代表有 cycle 存在
        return count == numCourses
  • 成效 :
    • Time Complexity : $O(V + E)$
    • Runtime: 63 ms (faster than 90.73%)
    • Memory Usage: 14.6 MB (more than 95.48%)