# Leetcode 207. Course Schedule

## 拓墣排序

### BFS

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        edges = [[] for i in range(numCourses)] # 紀錄所有節點的相鄰節點
        in_degree = [0] * numCourses # 紀錄所有節點剩餘的入分支度
        queue = [] # 紀錄入度為零的所有節點，等待排序
        visited = 0 # 紀錄拓墣排序訪問過的節點數

        # 紀錄所有節點的入度和相鄰節點
        for pre in prerequisites:
            edges[pre[1]].append(pre[0])
            in_degree[pre[0]] += 1
        
        # 逐一比對是否有入度為零的節點，如果有代表可以進行拓墣排序
        for i in range(numCourses):
            if in_degree[i] == 0:
                queue.append(i)
                visited += 1
        # 開始處理佇列中可進行拓墣排序的節點 
        while queue:
            node = queue.pop(0) # 從佇列裡彈出節點處理
            for n in edges[node]: # 逐一刪除節點所有的邊，並且同步更新相鄰節點的入度
                in_degree[n] -= 1
                if in_degree[n] == 0: # 如果入度為零，就代表可以進行拓墣排序，加入佇列中，並且更新訪問節點數字
                    queue.append(n)
                    visited += 1
        
        return visited == numCourses # 驗證修課總數是否和訪問總數一樣

## DFS

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for i in range(numCourses)]
        color = [0] * numCourses
        visited = 0

        def dfs(node: int, graph: List[List[int]], color: List[int]):
            color[node] = 1

            for neighbor in graph[node]:
                if color[neighbor] == 0:
                    check = dfs(neighbor,graph,color)
                    if not check:
                        return False
                elif color[neighbor] == 1:
                    return False
            
            color[node] = 2

            return True


        for ai,bi in prerequisites:
            graph[bi].append(ai)

        for node in range(numCourses):
            if color[node] == 0:
                check = dfs(node,graph,color)
                if not check:
                    return False
                visited += 1
            elif color[node] == 2:
                visited += 1

        return visited == numCourses