代碼隨想錄二刷之“圖論”～GO

A.深搜與廣搜（重點掌握！！！！）

深搜類似于回溯法

搜索方向，是認準一個方向搜，直到碰壁之后再換方向
換方向是撤銷原路徑，改為節點鏈接的下一個路徑，回溯的過程。

廣搜能保存我們要遍歷過的元素的容器就可以，隊列、棧、數組都是OK。

用隊列的話，就是保證每一圈都是一個方向去轉，例如統一順時針或者逆時針。因為隊列是先進先出，加入元素和彈出元素的順序是沒有改變的。
如果用棧的話，就是第一圈順時針遍歷，第二圈逆時針遍歷，第三圈有順時針遍歷。因為棧是先進后出，加入元素和彈出元素的順序改變了

1.可達路徑

感悟：找出從1到5的所有路徑，深度優先搜索的代碼其實和回溯法很像，節點入path，遞歸+回溯

var result [][]int 
var path []int     
func dfs(graph [][]int, x, n int) {// 當前遍歷的節點x 到達節點nif x == n { // 找到符合條件的一條路徑temp := make([]int, len(path))copy(temp, path)result = append(result, temp)return}for i := 1; i <= n; i++ { // 遍歷節點x鏈接的所有節點if graph[x][i] == 1 { // 找到 x鏈接的節點path = append(path, i)    // 遍歷到的節點加入到路徑中來dfs(graph, i, n)          // 進入下一層遞歸path = path[:len(path)-1] // 回溯，撤銷本節點}}
}

2.島嶼數量

方法一：深搜---模板題，后期要總結！！！！

package main
import "fmt"var dir = [][]int{{0, 1},   // 右{1, 0},   // 下{-1, 0},  // 上{0, -1},  // 左
}
func dfs(graph [][]int, visited [][]bool,x,y int){for i := range dir{nextx := x + dir[i][0]nexty := y + dir[i][1]if nextx < 0||nextx >= len(graph)||nexty < 0||nexty >=len(graph[0]){continue}if !visited[nextx][nexty] && graph[nextx][nexty] == 1{visited[nextx][nexty] = truedfs(graph,visited,nextx,nexty)}}
}
func main(){var n,m intfmt.Scan(&n,&m)graph := make([][]int,n)for i := range graph{graph[i] = make([]int,m)}for i := 0;i < n; i++{for j := 0;j < m; j++{fmt.Scan(&graph[i][j])}}visited := make([][]bool,n)for i := range visited{visited[i] = make([]bool,m)}var res intfor i := 0;i < n;i++{for j := 0;j < m;j++{if !visited[i][j] && graph[i][j] == 1{visited[i][j] = trueres++dfs(graph,visited,i,j)//將和他相連的陸地都標記上true}}}fmt.Println(res)
}

方法二：廣搜---模板題---后期要總結！！！

package main
import ("fmt""container/list"
)var dir = [4][2]int{{0, 1},   // 右{1, 0},   // 下{-1, 0},  // 上{0, -1},  // 左
}
func bfs(graph [][]int, visited [][]bool,x,y int){queue := list.New()queue.PushBack([2]int{x,y})visited[x][y] = truefor queue.Len() > 0{cur := queue.Remove(queue.Front()).([2]int)curx,cury := cur[0],cur[1]for i := range dir{nextx := curx + dir[i][0]nexty := cury + dir[i][1]if nextx < 0 || nexty < 0||nextx >= len(graph)||nexty >= len(graph[0]){continue}if !visited[nextx][nexty] && graph[nextx][nexty] == 1{visited[nextx][nexty] = truequeue.PushBack([2]int{nextx,nexty})}}}
}func main(){var n,m intfmt.Scan(&n,&m)graph := make([][]int,n)for i := range graph{graph[i] = make([]int,m)}for i := 0;i < n;i++{for j := 0;j < m;j++{fmt.Scan(&graph[i][j])}}visited := make([][]bool,n)for i := range visited{visited[i] = make([]bool,m)}var res intfor i := 0;i < n;i++{for j := 0;j < m;j++{if !visited[i][j] && graph[i][j] == 1{visited[i][j] = trueres++bfs(graph,visited,i,j)//將和他相連的陸地都標記上true}}}fmt.Println(res)
}

3.島嶼最大面積

感悟：本題就在模板題的基礎之上統計面積！！！

package main
import "fmt"var dir = [][]int{{0, 1},   // 右{1, 0},   // 下{-1, 0},  // 上{0, -1},  // 左
}
var count int
func dfs(graph [][]int, visited [][]bool,x,y int){for i := range dir{nextx := x + dir[i][0]nexty := y + dir[i][1]if nextx < 0||nextx >= len(graph)||nexty < 0||nexty >=len(graph[0]){continue}if !visited[nextx][nexty] && graph[nextx][nexty] == 1{visited[nextx][nexty] = truecount++dfs(graph,visited,nextx,nexty)}}
}
func max(i,j int)int{if i > j{return i}else{return j}
}
func main(){var n,m intfmt.Scan(&n,&m)graph := make([][]int,n)for i := range graph{graph[i] = make([]int,m)}for i := 0;i < n; i++{for j := 0;j < m; j++{fmt.Scan(&graph[i][j])}}visited := make([][]bool,n)for i := range visited{visited[i] = make([]bool,m)}var res intfor i := 0;i < n;i++{for j := 0;j < m;j++{if !visited[i][j] && graph[i][j] == 1{visited[i][j] = truecount = 1dfs(graph,visited,i,j)res = max(res,count)//將和他相連的陸地都標記上true}}}fmt.Println(res)
}

4.孤島總面積

本題要求找到不靠邊的陸地面積，那么我們只要從周邊找到陸地然后通過 dfs或者bfs 將周邊靠陸地且相鄰的陸地都變成海洋，然后再去重新遍歷地圖統計此時還剩下的陸地就可以了。

package mainimport ("container/list""fmt"
)// 四個方向的偏移量
var dir = [][]int{{0, 1},   // 右{1, 0},   // 下{-1, 0},  // 上{0, -1},  // 左
}// BFS函數，用于標記并清除連通的陸地
func bfs(grid [][]int, x, y int) {// 使用list作為隊列que := list.New()que.PushBack([2]int{x, y})grid[x][y] = 0 // 加入隊列后立即標記為已訪問// 隊列不為空時繼續處理for que.Len() > 0 {// 取出隊首元素cur := que.Front().Value.([2]int)que.Remove(que.Front())curx, cury := cur[0], cur[1]// 遍歷四個方向for i := 0; i < 4; i++ {nextx := curx + dir[i][0]nexty := cury + dir[i][1]// 邊界檢查if nextx < 0 || nextx >= len(grid) || nexty < 0 || nexty >= len(grid[0]) {continue}// 如果是未訪問的陸地，加入隊列并標記if grid[nextx][nexty] == 1 {que.PushBack([2]int{nextx, nexty})grid[nextx][nexty] = 0 // 加入隊列后立即標記}}}
}func main() {var n, m intfmt.Scan(&n, &m)// 初始化網格grid := make([][]int, n)for i := range grid {grid[i] = make([]int, m)}// 讀取網格數據for i := 0; i < n; i++ {for j := 0; j < m; j++ {fmt.Scan(&grid[i][j])}}// 處理左右邊界的陸地for i := 0; i < n; i++ {if grid[i][0] == 1 {bfs(grid, i, 0)}if grid[i][m-1] == 1 {bfs(grid, i, m-1)}}// 處理上下邊界的陸地for j := 0; j < m; j++ {if grid[0][j] == 1 {bfs(grid, 0, j)}if grid[n-1][j] == 1 {bfs(grid, n-1, j)}}// 統計剩余的陸地（孤島）數量count := 0for i := 0; i < n; i++ {for j := 0; j < m; j++ {if grid[i][j] == 1 {count++}}}fmt.Println(count)
}

5.沉沒孤島

感悟：這道題只不過遇到陸地就加一，最后都減1。和上道題一個思路

package mainimport ("container/list""fmt"
)// 四個方向的偏移量
var dir = [][]int{{0, 1},   // 右{1, 0},   // 下{-1, 0},  // 上{0, -1},  // 左
}// BFS函數，用于標記并清除連通的陸地
func bfs(grid [][]int, x, y int) {// 使用list作為隊列que := list.New()que.PushBack([2]int{x, y})grid[x][y] = 2 // 加入隊列后立即標記為已訪問// 隊列不為空時繼續處理for que.Len() > 0 {// 取出隊首元素cur := que.Front().Value.([2]int)que.Remove(que.Front())curx, cury := cur[0], cur[1]// 遍歷四個方向for i := 0; i < 4; i++ {nextx := curx + dir[i][0]nexty := cury + dir[i][1]// 邊界檢查if nextx < 0 || nextx >= len(grid) || nexty < 0 || nexty >= len(grid[0]) {continue}// 如果是未訪問的陸地，加入隊列并標記if grid[nextx][nexty] == 1 {que.PushBack([2]int{nextx, nexty})grid[nextx][nexty] = 2 // 加入隊列后立即標記}}}
}func main() {var n, m intfmt.Scan(&n, &m)// 初始化網格grid := make([][]int, n)for i := range grid {grid[i] = make([]int, m)}// 讀取網格數據for i := 0; i < n; i++ {for j := 0; j < m; j++ {fmt.Scan(&grid[i][j])}}// 處理左右邊界的陸地for i := 0; i < n; i++ {if grid[i][0] == 1 {bfs(grid, i, 0)}if grid[i][m-1] == 1 {bfs(grid, i, m-1)}}// 處理上下邊界的陸地for j := 0; j < m; j++ {if grid[0][j] == 1 {bfs(grid, 0, j)}if grid[n-1][j] == 1 {bfs(grid, n-1, j)}}// 統計剩余的陸地（孤島）數量for i := 0; i < n; i++ {for j := 0; j < m; j++ {if grid[i][j] != 0 {grid[i][j]--}}}for i := 0;i < n;i++{for j := 0;j < m-1;j++{fmt.Printf("%d ",grid[i][j])}fmt.Println(grid[i][m-1])}
}

6.水流問題

從第一組邊界逆流而上，第二組邊界也逆流而上，然后同時標記過的點就是答案

package mainimport "fmt"var n, m int
var dir = [][]int{{-1, 0}, // 上{0, -1}, // 左{1, 0},  // 下{0, 1},  // 右
}// dfs 函數：從(x,y)開始遍歷，只向不低于當前高度的方向移動
func dfs(grid [][]int, visited [][]bool, x, y int) {if visited[x][y] {return}visited[x][y] = truefor i := 0; i < 4; i++ {nextx := x + dir[i][0]nexty := y + dir[i][1]// 邊界檢查if nextx < 0 || nextx >= n || nexty < 0 || nexty >= m {continue}// 只向不低于當前高度的方向遍歷（從低向高）if grid[x][y] > grid[nextx][nexty] {continue}dfs(grid, visited, nextx, nexty)}
}func main() {fmt.Scan(&n, &m)// 初始化網格grid := make([][]int, n)for i := range grid {grid[i] = make([]int, m)}// 讀取網格數據for i := 0; i < n; i++ {for j := 0; j < m; j++ {fmt.Scan(&grid[i][j])}}// 初始化兩個邊界訪問標記數組firstBorder := make([][]bool, n)secondBorder := make([][]bool, n)for i := range firstBorder {firstBorder[i] = make([]bool, m)secondBorder[i] = make([]bool, m)}// 從最左列和最右列開始遍歷for i := 0; i < n; i++ {dfs(grid, firstBorder, i, 0)          // 第一組邊界：最左列dfs(grid, secondBorder, i, m-1)       // 第二組邊界：最右列}// 從最上行和最下行開始遍歷for j := 0; j < m; j++ {dfs(grid, firstBorder, 0, j)          // 第一組邊界：最上行dfs(grid, secondBorder, n-1, j)       // 第二組邊界：最下行}// 輸出同時被兩組邊界遍歷到的節點坐標for i := 0; i < n; i++ {for j := 0; j < m; j++ {if firstBorder[i][j] && secondBorder[i][j] {fmt.Printf("%d %d\n", i, j)}}}
}

7.建造最大孤島

package mainimport "fmt"var n, m int
var dir = [][]int{{-1, 0}, // 上{0, -1}, // 左{1, 0},  // 下{0, 1},  // 右
}// dfs 函數：從(x,y)開始遍歷，只向不低于當前高度的方向移動
func dfs(grid [][]int, visited [][]bool, x, y int) {if visited[x][y] {return}visited[x][y] = truefor i := 0; i < 4; i++ {nextx := x + dir[i][0]nexty := y + dir[i][1]// 邊界檢查if nextx < 0 || nextx >= n || nexty < 0 || nexty >= m {continue}// 只向不低于當前高度的方向遍歷（從低向高）if grid[x][y] > grid[nextx][nexty] {continue}dfs(grid, visited, nextx, nexty)}
}func main() {fmt.Scan(&n, &m)// 初始化網格grid := make([][]int, n)for i := range grid {grid[i] = make([]int, m)}// 讀取網格數據for i := 0; i < n; i++ {for j := 0; j < m; j++ {fmt.Scan(&grid[i][j])}}// 初始化兩個邊界訪問標記數組firstBorder := make([][]bool, n)secondBorder := make([][]bool, n)for i := range firstBorder {firstBorder[i] = make([]bool, m)secondBorder[i] = make([]bool, m)}// 從最左列和最右列開始遍歷for i := 0; i < n; i++ {dfs(grid, firstBorder, i, 0)          // 第一組邊界：最左列dfs(grid, secondBorder, i, m-1)       // 第二組邊界：最右列}// 從最上行和最下行開始遍歷for j := 0; j < m; j++ {dfs(grid, firstBorder, 0, j)          // 第一組邊界：最上行dfs(grid, secondBorder, n-1, j)       // 第二組邊界：最下行}// 輸出同時被兩組邊界遍歷到的節點坐標for i := 0; i < n; i++ {for j := 0; j < m; j++ {if firstBorder[i][j] && secondBorder[i][j] {fmt.Printf("%d %d\n", i, j)}}}
}

8.島嶼周長

package mainimport ("bufio""fmt""os""strconv""strings"
)func main() {scanner := bufio.NewScanner(os.Stdin)scanner.Scan()line := scanner.Text()n, m := parseInput(line)// 初始化 gridgrid := make([][]int, n)for i := range grid {grid[i] = make([]int, m)}// 讀入 grid 數據for i := 0; i < n; i++ {scanner.Scan()line := scanner.Text()values := parseLine(line, m)for j := 0; j < m; j++ {grid[i][j] = values[j]}}sum := 0   // 陸地數量cover := 0 // 相鄰數量for i := 0; i < n; i++ {for j := 0; j < m; j++ {if grid[i][j] == 1 {sum++ // 統計總的陸地數量// 統計上邊相鄰陸地if i-1 >= 0 && grid[i-1][j] == 1 {cover++}// 統計左邊相鄰陸地if j-1 >= 0 && grid[i][j-1] == 1 {cover++}// 為什么沒統計下邊和右邊？ 因為避免重復計算}}}fmt.Println(sum*4 - cover*2)
}// parseInput 解析 n 和 m
func parseInput(line string) (int, int) {parts := strings.Split(line, " ")n, _ := strconv.Atoi(parts[0])m, _ := strconv.Atoi(parts[1])return n, m
}// parseLine 解析一行中的多個值
func parseLine(line string, count int) []int {parts := strings.Split(line, " ")values := make([]int, count)for i := 0; i < count; i++ {values[i], _ = strconv.Atoi(parts[i])}return values
}

9.字符串接龍

1、圖中的線是如何連在一起的

在搜索的過程中，我們可以枚舉，用26個字母替換當前字符串的每一個字符，在看替換后是否在 strList里出現過，就可以判斷兩個字符串是否是鏈接的。

2、起點和終點的最短路徑長度

首先題目中并沒有給出點與點之間的連線，而是要我們自己去連，條件是字符只能差一個。所以判斷點與點之間的關系，需要判斷是不是差一個字符，如果差一個字符，那就是有鏈接。然后就是求起點和終點的最短路徑長度，在無權圖中，求最短路，用深搜或者廣搜就行，沒必要用最短路算法。在無權圖中，用廣搜求最短路最為合適，廣搜只要搜到了終點，那么一定是最短的路徑。因為廣搜就是以起點中心向四周擴散的搜索。

另外需要有一個注意點：

本題是一個無向圖，需要用標記位，標記著節點是否走過，否則就會死循環！
使用哈希表來檢查字符串是否出現在字符串集合里更快一些

這道題好難啊！！！（需要二刷）

package main
import("fmt"
)
var count int
func bfs(start,end string,strset map[string]bool)int{visited := make(map[string]int)que := []string{start}visited[start] = 1for len(que) > 0{word := que[0]que = que[1:]path := visited[word]for i := 0;i < len(word);i++{newWord := []byte(word)for j := 0;j < 26;j++{newWord[i] = byte('a'+j)newString := string(newWord)if newString == end{return path + 1}if strset[newString] && visited[newString]==0{//當前單詞沒有遍歷過且新單詞在給定的集合當中visited[newString] = path + 1que = append(que,newString)}}}}return 0//沒找到
}func main(){var num intfmt.Scan(&num)var start,end,str stringfmt.Scan(&start,&end)strset := make(map[string]bool,num)for i := 0;i < num;i++{fmt.Scan(&str)strset[str] = true}result := bfs(start,end,strset)fmt.Println(result)
}

10.有向圖的完全可達性

如果是無權的。鄰接矩陣就是：如果a和b相連接，a和c連接，那么graph[a][b] = 1.graph[a][c] = 1。如果是鄰接表，那么graph[a] = [b,c]

思路：構建鄰接表，如果遇到了沒有經歷過的節點visited置為true。隨后遍歷他的鄰接表。如果遇到新的節點，就接著遞歸遍歷，并且置為true。直到最后。

package mainimport ("fmt"
)func dfs(graph [][]int, key int, visited []bool) {visited[key] = truefor _,neighbor := range graph[key]{if visited[neighbor] == false{dfs(graph,neighbor,visited)}}
}func main(){var n, k intfmt.Scan(&n, &k)//n個節點，k個邊graph := make([][]int,n+1)for i := 0;i < k;i++{var u,v intfmt.Scan(&u,&v)graph[u] = append(graph[u],v) }visited := make([]bool,n+1)dfs(graph,1,visited)for i := 1; i <= n; i++ {if !visited[i] {fmt.Println(-1)return}}fmt.Println(1)
}

11.單詞接龍

感悟：這道題的本質和字符串接龍是一模一樣的。。下午刷完，晚上看這道題就暈了。類似于層序遍歷。

func ladderLength(beginWord string, endWord string, wordList []string) int {wordSet := make(map[string]bool,len(wordList))for _,word := range wordList{wordSet[word] = true}if !wordSet[endWord]{return 0}visited := make(map[string]int)visited[beginWord] = 1que := []string{beginWord}for len(que) > 0{cur := que[0]que = que[1:]//出隊列path := visited[cur]for i := 0;i < len(cur);i++{newstr := []byte(cur)for j := 0;j < 26;j++{newstr[i] = byte('a'+j)nextword := string(newstr)if nextword == endWord{return path + 1//找到了}if visited[nextword] == 0 && wordSet[nextword]{//能找到，但是沒有遍歷過visited[nextword] = path + 1que = append(que,nextword)}}}}    return 0
}

12.鑰匙和房間

感悟：這道題的本質就是圖的連通性的問題。每個房間對應個節點，房間里的鑰匙對應節點間的“邊”。所以即轉換成起始節點遍歷所有節點。選擇DFS，是因為很契合DFS的邏輯“深度優先，遞歸探索。”

func canVisitAllRooms(rooms [][]int) bool {visited := make([]bool,len(rooms))var dfs func(key int)dfs = func(key int){if visited[key]{return}visited[key] = truefor _,i := range rooms[key]{dfs(i)}}dfs(0)for i := range visited{if visited[i] == false{return false}}return true
}

B.并查集

并查集主要有兩個功能：

將兩個元素添加到一個集合中。
判斷兩個元素在不在同一個集合

并查集模板

package mainimport ("fmt"
)const MaxNodes = 101var n int
var father [MaxNodes]int// 初始化并查集
func initialize() {for i := 1; i <= n; i++ {father[i] = i}
}// 并查集里尋根的過程
func find(u int) int {if u == father[u] {return u}father[u] = find(father[u])return father[u]
}// 判斷 u 和 v 是否找到同一個根
func isSame(u, v int) bool {return find(u) == find(v)
}// 將 v->u 這條邊加入并查集
func join(u, v int) {rootU := find(u)rootV := find(v)if rootU != rootV {father[rootV] = rootU}
}func main() {var m, s, t, source, destination intfmt.Scan(&n, &m)initialize()for i := 0; i < m; i++ {fmt.Scan(&s, &t)join(s, t)}fmt.Scan(&source, &destination)if isSame(source, destination) {fmt.Println(1)} else {fmt.Println(0)}
}

1.冗余連接

方法一深搜：每遍歷一條邊的時候，比如[u,v]，首先判斷u是否能與v連通。如果不能，將其放入連通表中。如果可以連通，那就把那條邊返回。對于深搜的思路：比如判斷2和3能不能連通。遍歷2的連通表，比如數字是1.然后接著就去判斷1和3的連通性了。如果在1的連通表的可以找到3，那么就說明2，3連通。然后遞歸返回。

func findRedundantConnection(edges [][]int) []int {graph := make(map[int][]int)visited := make(map[int]bool)var dfs func(u, v int) booldfs = func(u, v int) bool {if u == v {return true}visited[u] = truefor _, next := range graph[u] {if !visited[next] {// 關鍵修復：如果遞歸找到路徑，立即返回trueif dfs(next, v) {return true}}}return false}for _, edge := range edges {u, v := edge[0], edge[1]// 重置訪問標記for node := range visited {visited[node] = false}if dfs(u, v) {return []int{u, v}}// 將當前邊加入圖中graph[u] = append(graph[u], v)graph[v] = append(graph[v], u)}return []int{}
}

方法二：并查集：

首先記住并查集的初始化方式，還有find函數的思想。然后就一次遍歷邊集的，然后查看x和y是否有同一個根節點。如果有了，就證明再加那條邊就冗余了。

func findRedundantConnection(edges [][]int) []int {parent := make([]int,len(edges) + 1)// 初始化并查集，每個節點的父節點指向自己for i := 1;i <= len(edges);i++{parent[i] = i}// 查找根節點（帶路徑壓縮）var find func(int) intfind = func(x int) int {if parent[x] != x {parent[x] = find(parent[x]) // 路徑壓縮}return parent[x]
//處理當前邏輯：對于parent[x]通過若干的遞歸和回溯，已經找到了目前他所對應的根節點了。所以直接返回}for _,edge := range edges{u,v := edge[0],edge[1]rootU := find(u)rootV := find(v)if rootU == rootV{return edge}parent[rootV] = rootU}return nil
}

處理當前層邏輯：在遞歸調用返回后，利用返回的結果來完成當前層需要完成的任務。

拓撲排序的過程

找到入度為0 的節點，加入結果集
將該節點從圖中移除

循環以上兩步，直到所有節點都在圖中被移除了。結果集的順序，就是我們想要的拓撲排序順序?

拓撲排序判斷有沒有環：0加入到結果集之后，找不到入度為0的點

C.最小生成樹理論

prim && kruskal

感覺面試不怎么考。。。

D.拓撲排序

拓撲排序指的是一種解決問題的大體思路，而具體算法，可能是廣搜也可能是深搜。

1.課程表

func canFinish(numCourses int, prerequisites [][]int) bool {inDegree := make([]int,numCourses)//入度graph := make([][]int,numCourses)//鄰接表for _,pre := range prerequisites{//初始化course,precourse := pre[0],pre[1]graph[precourse] = append(graph[precourse],course)inDegree[course]++}queue := []int{}for i := 0;i < numCourses;i++{//入度為0點點加入隊列if inDegree[i] == 0{queue = append(queue,i)}}count := 0for len(queue) > 0{cur := queue[0]queue = queue[1:]count++// 遍歷當前課程的所有后續課程for _,nextCourse := range graph[cur]{inDegree[nextCourse]--if inDegree[nextCourse] == 0{queue = append(queue,nextCourse)}}}return count == numCourses
}

2.課程表2??

方法一：開兩個數組（冗余）方法二：

func findOrder(numCourses int, prerequisites [][]int) []int {inDegree := make([]int, numCourses)graph := make(map[int][]int)for _, val := range prerequisites {course, precourse := val[0], val[1]inDegree[course]++graph[precourse] = append(graph[precourse], course)}res := []int{}// 第一輪：添加所有入度為0的課程for i := 0; i < numCourses; i++ {if inDegree[i] == 0 {res = append(res, i)}}// 使用res作為隊列，i作為指針for i := 0; i < len(res); i++ {cur := res[i]for _, next := range graph[cur] {inDegree[next]--if inDegree[next] == 0 {res = append(res, next)}}}if len(res) != numCourses {return []int{}}return res
}

感悟：這也太優雅了吧。len(res)?在循環過程中會不斷增長。res同時充當結果容器去存儲結果，同時i也相當于指針去標記當前處理的位置