207. 課程表

題目描述：你這個學期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。
在選修某些課程之前需要一些先修課程。 先修課程按數組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學習課程 ai 則 必須 先學習課程 bi 。
例如，先修課程對 [0, 1] 表示：想要學習課程 0 ，你需要先完成課程 1 。
請你判斷是否可能完成所有課程的學習？如果可以，返回 true ；否則，返回 false 。

考察重點：拓撲排序

方法概括：利用二維數組que保存每一結點的所有前置結點，flag記錄每一結點是否安全，最后使用DFS循環遍歷所有路徑。

func dfs(flag []int, que [][]int, lenque []int, num int) bool {if flag[num] == -1 { //如果為-1，說明成環return false} else if flag[num] == 1 { //如果為1，說明該節點是安全節點return true}flag[num] = -1 //標記為-1，表示待定，在該次深度遍歷中已經出現過一次，如果再次出現這說明成環for i := 0; i < lenque[num]; i++ { //循環遍歷指向num節點的所有節點，如果都是安全的，則num是安全的（如下將其置為1）if !dfs(flag, que, lenque, que[num][i]) {return false}}flag[num] = 1return true }func CanFinish(numCourses int, prerequisites [][]int) bool {var que [][]intfor x := 0; x < numCourses; x++ {ar := make([]int, numCourses)que = append(que, ar)}flag := make([]int, numCourses) //flag 標記該節點是否為安全節點，1——安全，-1——不安全(待定)，0——還未檢測lenque := make([]int, numCourses) //記錄每個que長度for i := 0; i < len(prerequisites); i++ {temp := prerequisites[i][1] //que[i][] 記錄指向i的所有節點 lenque 記錄每一個que[i][]的長度que[temp][lenque[temp]] = prerequisites[i][0]lenque[temp]++// temp := prerequisites[i][0] //結果一樣的// que[temp][lenque[temp]] = prerequisites[i][1]// lenque[temp]++}// fmt.Print(lenque)for i := 0; i < numCourses; i++ { //保障所有節點都被遍歷過，非-1即1，保障沒有0if !dfs(flag, que, lenque, i) {return false}}return true }

總結

以上是生活随笔為你收集整理的LeetCode—207. 课程表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。