破題

本題要求找出一種課程學習順序，使得每一門課程都在它的先修課程之後學習。這可以用一種叫做「拓撲排序」的方法來解決。

• 有向圖是一種由節點和箭頭組成的圖，箭頭表示節點之間的方向關係。
• 拓撲排序是一種對有向圖中的節點進行排序的方法，它要求對於任意一條有向邊 ，節點 必須在節點 之前出現在排序中。

我們可以把每一門課程看成一個節點，把先修課程的要求看成一條箭頭，指向要學習的課程。例如，如果要學習課程 之前必須完成課程 ，那麽我們就畫一條從 指向 的箭頭。這樣我們就得到了一個有向圖，表示所有課程之間的依賴關係。

如果這個有向圖中沒有形成任何循環，也就是沒有一些互相依賴的課程，那麽我們就可以用拓撲排序的方法找出一種合理的學習順序，使得每一門課程都在它的先修課程之後學習。如果這個有向圖中存在循環，那麽就表示沒有辦法完成所有的課程，也就不存在拓撲排序了。

拓撲排序的方法有很多種，例如深度優先搜尋和廣度優先搜尋。這裡不詳細介紹具體的算法流程，只給出一些基本的思路：

• 深度優先搜尋是一種從某個節點出發，不斷探索它沒有訪問過的相鄰節點的方法。在這個過程中，我們可以用一個堆疊來存儲已經訪問過的節點。當我們回溯到某個節點時，表示它的所有相鄰節點都已經訪問過了，那麽我們就可以把它放入堆疊中。最後從堆疊底到堆疊頂的順序就是一種拓撲排序。
• 廣度優先搜尋是一種從某些節點出發，按照距離遠近依次訪問它們的相鄰節點的方法。在這個過程中，我們可以用一個 queue 來存儲沒有任何 in-degree（先修課程要求）的節點，也就是可以直接學習的課程。每次我們從 queue 中取出一個節點，把它放入答案中，並且刪除它指向的所有節點的 in-degree。如果某個節點刪除了所有的 in-degree，那麽它就可以加入 queue 中。最後，queue 從頭到尾的順序就是一種拓撲排序。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！ 立即加入「面試讀書會」，和大家一起準備面試！

內推機會	加入讀書會 (邀請碼：7456)

廣度優先搜尋 (BFS)

• 廣度優先搜尋的方法，從 in-degree 為零的節點（沒有先修課程要求的節點）開始，依次將它們加入 queue 中，並造訪它們所有的鄰居（代表完成了一門先修課程要求的後續課程）
• 如果在搜尋過程中，某個節點的 in-degree 都被造訪過了，那麼就將它加入 queue 中，等待下一輪的搜尋。
• 如果最終能夠得到 個節點的拓撲排序，那麼就回傳這個排序，否則回傳空陣列表示不存在拓撲排序（圖中存在循環）。

演算法

• 定義兩個函數 buildGraph 和 buildDepGraph ，分別用於建立有向圖和紀錄每個節點的 in-degree。
• 定義一個佇列 queue 用於廣度優先搜尋，並將所有 in-degree 為零的節點加入 queue 中。
• 定義一個集合 visited 用於記錄已經訪問過的節點，並將所有 in-degree 為零的節點加入集合中。
• 定義一個列表 result 用於存儲拓撲排序的結果。
• 當 queue 不為空時，重複以下步驟：
  • 從 queue 中取出一個節點 node ，並將它加入 result 中。
  • 遍歷 node 的所有相鄰節點 it。
  • 如果 it 還沒有被訪問過，並且 it 的 in-degree 變都被造訪過了，那麼將 it 加入queue 和 visited 中。
• 如果 result 的大小等於 ，那麼回傳 result ，否則回傳空陣列。

程式

class Solution {
    fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
        val graph = buildGraph(numCourses, prerequisites)
        val depGraph = buildDepGraph(numCourses, prerequisites)
        val freeNodes = (0 until numCourses).filter { c -> c !in prerequisites.map { it[0] } }
        val queue: Queue<Int> = LinkedList()
        val visited = mutableSetOf<Int>()
        freeNodes.forEach {
            queue.offer(it)
            visited.add(it)
        }
        val result = mutableListOf<Int>()
        while (queue.isNotEmpty()) {
            for (i in queue.indices) {
                val node = queue.poll()
                result.add(node)
                graph[node]!!.forEach {
                    if (!visited.contains(it)) {
                        if (depGraph[it]!!.all { visited.contains(it) }) {
                            queue.offer(it)
                            visited.add(it)
                        }
                    }
                }
            }
        }
         return if(result.size != numCourses) intArrayOf() else result.toIntArray()
    }

    fun buildGraph(numCourses: Int, prerequisites: Array<IntArray>): Map<Int, List<Int>> {
        val result = mutableMapOf<Int, List<Int>>()
        for (i in 0 until numCourses) {
            result[i] = emptyList()
        }
        prerequisites.forEach {
            result[it[1]] = result[it[1]]!! + it[0]
        }
        return result
    }

    fun buildDepGraph(numCourses: Int, prerequisites: Array<IntArray>): Map<Int, List<Int>> {
        val result = mutableMapOf<Int, List<Int>>()
        for (i in 0 until numCourses) {
            result[i] = emptyList()
        }
        prerequisites.forEach {
            result[it[0]] = result[it[0]]!! + it[1]
        }
        return result
    }
}

複雜度分析

• 時間複雜度:
  ，其中 是課程數， 是先修課程的要求數。這個複雜度是因為我們要把所有的課程和要求都檢查一遍，找出可以學習的順序。

• 空間複雜度:
  ，這個複雜度是因為我們要用兩個 hash table 來存儲每個課程的相鄰課程和先修課程，hash table 的大小都是 。另外，我們還要用一個 queue 來存儲可以學習的課程、一個集合來存儲已經學習過的課程，和一個列表來存儲最終的答案，這些空間都是 。

　更多 LeetCode 解答在此，一起來學習！

內推機會來啦！

跟一流的人才幹大事，享受成功進步的高級樂趣！

內推機會	加入讀書會 (邀請碼：7456)