# Leetcode 210. Coruse Schedule II

## 拓墣排序

### BFS

入度為零即可加入答案中

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        edges = [[] for i in range(numCourses)]
        in_degree = [0] * numCourses
        result = []
        queue = []

        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) # 入度為零，加入拓墣排序進入點
                result.append(i)
        
        while queue:
            node = queue.pop(0)
            for n in edges[node]: # 訪問每個鄰居
                in_degree[n] -= 1 # 斷邊
                if in_degree[n] == 0: # 入度為零，加入答案中
                    queue.append(n) # 入度為零，可作為下一次拓墣排序的進入點
                    result.append(n)

        if len(result) == numCourses: # 最後檢查結果是否等同於節點
            return result
        else: # 如果節點數量不一致，代表有環或是有節點沒有邊，根據題意返回空陣列
            return []

### DFS

把節點分為三種狀態：
1. 0 （未訪問）
1. 1 （已訪問）
1. 2 （已完成）

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 0 unvisited , 1 visited , 2 finished
        # 因為深度優先搜索的搜索結果剛好會和拓墣排序相等，所以直接做深度優先搜索
        graph = [[] for i in range(numCourses)]
        color = [0] * numCourses
        output = []

        def check(node):
            color[node] = 1
            neighbors = graph[node]
            for neighbor in neighbors:
                if color[neighbor] == 0: # 相鄰節點尚未被訪問過
                    check_result = check(neighbor)
                    if not check_result:
                        return False
                elif color[neighbor] == 1: # 相鄰節點被訪問過
                    return False
            
            color[node] = 2
            output.insert(0,node) # 因為深度優先搜索的結果順序為倒序，所以結果要插入到輸入的第一個位置

            return True

        # 構造相鄰列表
        for ai,bi in prerequisites:
            graph[bi].append(ai)

        for current in range(numCourses): # 逐一遍歷
            if color[current] == 0: # 尚未訪問過
                check_result = check(current)
                if not check_result: # 如果檢查失敗 (圖中有環)
                    return []

        return output