1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func bfs(参数) {
    // 定义队列
    // 起始节点入队
    for len(queue) != 0 {
        // 取队首元素
        for 选择：本节点所连接的其他节点 {
            // 处理节点
            // 新节点入队
        }
    }
}

1
2
3
4

func find(u int) int {
    if father[u] == u return u  // 如果根就是自己，直接返回
    else return find(father[u]) // 如果根不是自己，就根据数组下标一层一层向下找根
}

1
2
3
4
5

func isSame(a int, b int) bool {
    a = find(a)
    b = find(b)
    return a == b
}

1
2
3
4
5

// 并查集里寻根的过程
func find(u int) int {
    if father[u] == u return u
    else return father[u] = find(father[u]) // 路径压缩
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

var father []int

func validPath(n int, edges [][]int, source int, destination int) bool {
    father = make([]int, n)
    initial(n)
    for i := range edges {
        join(edges[i][0], edges[i][1])
    }
    return isSame(source, destination)
}

// 并查集初始化
func initial(n int) {
    for i := 0; i < n; i++ {
        father[i] = i
    }
}

// 并查集里寻根
func find(u int) int {
    if father[u] == u {
        return u
    }
    father[u] = find(father[u])
    return father[u]
}

// 判断a和b是否找到同一个根
func isSame(a int, b int) bool {
    a = find(a)
    b = find(b)
    return a == b
}

// 边a->b加入并差集
func join(a int, b int) {
    a = find(a)
    b = find(b)
    if a == b {
        return // 同根说明已经在一个集合里
    }
    father[a] = b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

var path []int  // 节点0到节点n-1的所有路径
var res [][]int // 节点0到节点n-1的一条路径

func allPathsSourceTarget(graph [][]int) [][]int {
    path = make([]int, 0) // 力扣中全局变量需要重新初始化，否则会携带之前测试case的答案
    res = make([][]int, 0)
    path = append(path, 0) // 从节点0出发
    dfs(graph, 0)
    return res
}
func dfs(graph [][]int, cur int) {
    // 终止条件:当前遍历节点是节点n-1
    if cur == len(graph)-1 {
        temp := make([]int, len(path))
        copy(temp, path)
        res = append(res, temp) // 将找到的一条路径加入结果集
        return
    }
    for i := 0; i < len(graph[cur]); i++ { // 遍历当前节点连接的所有节点
        path = append(path, graph[cur][i]) // 将遍历到的节点加入路径
        dfs(graph, graph[cur][i])          // 进入下一层递归
        path = path[:len(path)-1]          // 回溯 在路径中撤销本节点
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

var visited [][]bool

func numIslands(grid [][]byte) int {
    res := 0
    visited = make([][]bool, len(grid))
    for i := range visited {
        visited[i] = make([]bool, len(grid[i]))
    }
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == '1' && !visited[i][j] { // 遇到陆地节点且没有被标记过
                res += 1
                dfs(grid, i, j)
            }
        }
    }
    return res
}
func dfs(grid [][]byte, x int, y int) {
    if grid[x][y] == '0' || visited[x][y] { // 遇到海洋节点或标记过的节点
        return
    }
    visited[x][y] = true  // 标记节点
    if x != len(grid)-1 { // x没到最后一层
        dfs(grid, x+1, y) // 递归 向下探索
    }
    if y != len(grid[x])-1 { // y没到最后一列
        dfs(grid, x, y+1)    // 递归 向右探索
    }
    if x != 0 {             // x不是第一层
        dfs(grid, x-1, y)   // 递归 向上探索
    }
    if y != 0 {             // y不是第一列
        dfs(grid, x, y-1)   // 递归 向左探索
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func numIslands(grid [][]byte) int {
    res := 0
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == '1' { // 遇到陆地节点且没有被标记过
                res += 1
                dfs(grid, i, j)
            }
        }
    }
    return res
}
func dfs(grid [][]byte, x int, y int) {
    // 下标越界或遇到海洋节点
    if x < 0 || y < 0 || x == len(grid) || y == len(grid[x]) || grid[x][y] == '0' {
        return
    }
    grid[x][y] = '0'  // 标记节点
    dfs(grid, x+1, y) // 递归 向下探索
    dfs(grid, x, y+1) // 递归 向右探索
    dfs(grid, x-1, y) // 递归 向上探索
    dfs(grid, x, y-1) // 递归 向左探索
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func numIslands(grid [][]byte) int {
    res := 0
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == '1' { // 遇到陆地节点且没有被标记过
                res += 1
                bfs(grid, i, j)
            }
        }
    }
    return res
}
func bfs(grid [][]byte, x int, y int) {
    queue := make([][]int, 0)                           // 定义队列
    queue = append(queue, []int{x, y})                  // 起始节点入队
    move := [4][2]int{{1, 0}, {0, 1}, {0, -1}, {-1, 0}} // 下右左上
    for len(queue) != 0 {                               // 遍历队列
        node := queue[0]         // 取队首元素
        queue = queue[1:]        // 更新队列
        for i := 0; i < 4; i++ { // 遍历当前节点四周
            x = node[0] + move[i][0]
            y = node[1] + move[i][1]
            // 下标越界或遇到海洋节点
            if x < 0 || y < 0 || x == len(grid) || y == len(grid[x]) || grid[x][y] == '0' {
                continue
            }
            grid[x][y] = '0'                   // 标记节点
            queue = append(queue, []int{x, y}) // 入队
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

var area int

func maxAreaOfIsland(grid [][]int) int {
    res := 0
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == 1 {
                dfs(grid, i, j)
                res = max(res, area)
                area = 0 // 重置面积
            }
        }
    }
    return res
}
func dfs(grid [][]int, x int, y int) {
    if x < 0 || y < 0 || x == len(grid) || y == len(grid[x]) || grid[x][y] == 0 {
        return
    }
    grid[x][y] = 0    // 标记
    area += 1         // 统计面积
    dfs(grid, x+1, y) // 下
    dfs(grid, x, y+1) // 右
    dfs(grid, x-1, y) // 上
    dfs(grid, x, y-1) // 左
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

var area int
var arrived bool

func numEnclaves(grid [][]int) int {
    res := 0
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == 1 {
                dfs(grid, i, j)
                if !arrived {
                    res += area // 记录不能到达边界的面积
                }
                area = 0        // 重置
                arrived = false // 重置
            }
        }
    }
    return res
}
func dfs(grid [][]int, x int, y int) {
    if x < 0 || y < 0 || x == len(grid) || y == len(grid[x]) {
        arrived = true // 上一块陆地是边界
        return
    }
    if grid[x][y] == 0 {
        return
    }
    grid[x][y] = 0    // 标记
    area += 1         // 统计面积
    dfs(grid, x+1, y) // 下
    dfs(grid, x, y+1) // 右
    dfs(grid, x-1, y) // 上
    dfs(grid, x, y-1) // 左
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func numEnclaves(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    for i := 0; i < m; i++ {
        if grid[i][0] == 1 { // 第一列
            dfs(grid, i, 0)
        }
        if grid[i][n-1] == 1 { // 最后一列
            dfs(grid, i, n-1)
        }
    }
    for i := 0; i < n; i++ {
        if grid[0][i] == 1 { // 第一排
            dfs(grid, 0, i)
        }
        if grid[m-1][i] == 1 { // 最后一排
            dfs(grid, m-1, i)
        }
    }
    res := 0
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == 1 {
                res++
            }
        }
    }
    return res
}
func dfs(grid [][]int, x, y int) {
    if x < 0 || y < 0 || x == len(grid) || y == len(grid[0]) || grid[x][y] == 0 {
        return
    }
    grid[x][y] = 0
    dfs(grid, x+1, y)
    dfs(grid, x, y+1)
    dfs(grid, x-1, y)
    dfs(grid, x, y-1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func solve(board [][]byte) {
    for row := 0; row < len(board); row++ {
        if board[row][0] == 'O' { // 第一列
            dfs(board, row, 0)
        }
        if board[row][len(board[0])-1] == 'O' { // 最后一列
            dfs(board, row, len(board[0])-1)
        }
    }
    for col := 1; col < len(board[0])-1; col++ {
        if board[0][col] == 'O' { // 第一排去首尾剩下中间的
            dfs(board, 0, col)
        }
        if board[len(board)-1][col] == 'O' { // 最后一排去首尾剩下中间的
            dfs(board, len(board)-1, col)
        }
    }
    for i := range board {
        for j := range board[i] {
            if board[i][j] == 'A' {
                board[i][j] = 'O' // 恢复可以到达边界的陆地
            } else if board[i][j] == 'O' {
                board[i][j] = 'X' // 不能到达边界的陆地
            }
        }
    }
}
func dfs(board [][]byte, x int, y int) {
    if x < 0 || y < 0 || x == len(board) || y == len(board[x]) || board[x][y] == 'X' || board[x][y] == 'A' {
        return
    }
    board[x][y] = 'A'  // 标记该陆地
    dfs(board, x+1, y) // 下
    dfs(board, x, y+1) // 右
    dfs(board, x-1, y) // 上
    dfs(board, x, y-1) // 左
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

var visited [][][]bool
var ds = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}} // 四周偏移量

func pacificAtlantic(heights [][]int) [][]int {
    res := make([][]int, 0)
    visited = make([][][]bool, len(heights))
    for i := range visited {
        visited[i] = make([][]bool, len(heights[i]))
    }
    for i := range visited {
        for j := range visited[i] {
            visited[i][j] = make([]bool, 2)
        }
    }
    for row := 0; row < len(heights); row++ {
        dfs(heights, row, 0, 0)                 // 标记第一列太平洋
        dfs(heights, row, len(heights[0])-1, 1) // 标记最后一列大西洋
    }
    for col := 0; col < len(heights[0]); col++ {
        dfs(heights, 0, col, 0)              // 标记第一排太平洋
        dfs(heights, len(heights)-1, col, 1) // 标记最后一排大西洋
    }
    for i := range heights {
        for j := range heights[i] {
            if visited[i][j][0] && visited[i][j][1] {
                res = append(res, []int{i, j})
            }
        }
    }
    return res
}
func dfs(heights [][]int, x int, y int, sign int) {
    visited[x][y][sign] = true
    for _, move := range ds {
        nextX := x + move[0]
        nextY := y + move[1]
        if nextX < 0 || nextY < 0 || nextX == len(heights) || nextY == len(heights[nextX]) {
            continue // 索引越界
        }
        if heights[x][y] > heights[nextX][nextY] || visited[nextX][nextY][sign] {
            continue // 高度不合适或标记过
        }
        dfs(heights, nextX, nextY, sign)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

var ds = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
var mark int
var area int

func largestIsland(grid [][]int) int {
    res := 0
    mark = 2
    getSize := make(map[int]int)
    // 统计各个岛屿面积
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == 1 {
                dfs(grid, i, j)      // 遍历该岛屿
                getSize[mark] = area // 保存岛屿面积
                area = 0             // 置零
                mark++               // 标记值更新
            }
        }
    }
    // 遍历0得到最大面积
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == 0 {
                // 得到四周岛屿总面积
                total := 0
                accounted := make(map[int]bool)
                for _, move := range ds {
                    x := i + move[0]
                    y := j + move[1]
                    if x < 0 || y < 0 || x == len(grid) || y == len(grid[x]) || grid[x][y] == 0 {
                        continue // 索引越界或遇到海洋
                    } else if accounted[grid[x][y]] {
                        continue // 该岛屿被统计过
                    } else {
                        accounted[grid[x][y]] = true // 标记该岛屿
                        total += getSize[grid[x][y]] // 统计该岛屿面积
                    }
                }
                res = max(res, 1+total) // 更新最大面积
            }
        }
    }
    if res == 0 {
        return len(grid) * len(grid)
    }
    return res
}
func dfs(grid [][]int, x int, y int) {
    if x < 0 || y < 0 || x == len(grid) || y == len(grid[x]) || grid[x][y] != 1 {
        return // 索引越界或遇到海洋或标记过
    }
    grid[x][y] = mark // 标记陆地
    area++            // 岛屿面积更新
    for _, move := range ds {
        nextX := x + move[0]
        nextY := y + move[1]
        dfs(grid, nextX, nextY)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

func ladderLength(beginWord string, endWord string, wordList []string) int {
    // 记录到达各单词的路径长度
    length := make(map[string]int)
    // 初始化到达beginword的路径长度为1
    length[beginWord] = 1
    // 队列BFS
    queue := make([]string, 0)
    // 初始化beginword入队
    queue = append(queue, beginWord)
    // wordList转换为字典存储
    wordMap := make(map[string]int)
    for i, v := range wordList {
        wordMap[v] = i
    }
    // BFS
    for len(queue) != 0 {
        // 取队首
        word := queue[0]
        queue = queue[1:]
        // 逐个位置替换
        for i := 0; i < len(word); i++ {
            // 将不可变字符串转化为字符切片
            wordSlice := []rune(word)
            // 26个字母逐个试
            for j := 'a'; j <= 'z'; j++ {
                // 替换字符
                wordSlice[i] = j
                // 判断字典中是否有该单词
                if _, ok := wordMap[string(wordSlice)]; ok {
                    // 判断该单词是否未被遍历使用过
                    if _, ok := length[string(wordSlice)]; !ok {
                        // 判断是否到达最终单词
                        if string(wordSlice) == endWord {
                            return length[word] + 1
                        }
                        // 记录到达该单词的路径长度（在替换前单词路径长度基础上加一）
                        length[string(wordSlice)] = length[word] + 1
                        // 该单词入队
                        queue = append(queue, string(wordSlice))
                    }
                }
            }
        }
    }
    return 0
}
// 写法二
func ladderLength(beginWord string, endWord string, wordList []string) int {
    // BFS遍历
    queue := []string{beginWord}
    mp := map[string]int{}
    mp[beginWord] = 1
    for len(queue) != 0 {
        cur := queue[0]
        queue = queue[1:]
        // 判是否已到终点
        if cur == endWord {
            return mp[cur]
        }
        // 遍历字典中所有单词
        for _, word := range wordList {
            // 判字典中该单词是否已遍历过或与当前单词一致
            if _, ok := mp[word]; ok || cur == word {
                continue
            }
            // 判是否相差一个字符
            if isValid(cur, word) {
                mp[word] = mp[cur] + 1
                queue = append(queue, word)
            }
        }
    }
    return 0
}
func isValid(str1, str2 string) bool {
    cnt := 0
    for i := range str1 {
        if str1[i] != str2[i] {
            cnt++
        }
    }
    return cnt == 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func canVisitAllRooms(rooms [][]int) bool {
    accessible := make([]bool, len(rooms))
    accessible[0] = true            // 0号房间可进入
    queue := make([][]int, 0)       // 定义队列
    queue = append(queue, rooms[0]) // 0号房入队
    for len(queue) != 0 {
        room := queue[0]           // 取队首
        queue = queue[1:]          // 出队
        for _, key := range room { // 遍历本房间中钥匙
            if !accessible[key] { // 此房间未入过队
                accessible[key] = true            // 更新可进入状态
                queue = append(queue, rooms[key]) // 新房入队
            }
        }
    }
    for i := range accessible {
        if !accessible[i] {
            return false // 有房间无法进入
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func canVisitAllRooms(rooms [][]int) bool {
    accessible := make([]bool, len(rooms))
    accessible[0] = true     // 0号房间可进入
    queue := make([]int, 0)  // 定义队列
    queue = append(queue, 0) // 0号房入队
    for len(queue) != 0 {
        idx := queue[0]                    // 取队首
        queue = queue[1:]                  // 出队
        for _, key := range rooms[idx] {   // 遍历本房间中钥匙
            if !accessible[key] {          // 此房间未入过队
                accessible[key] = true     // 更新可进入状态
                queue = append(queue, key) // 新房入队
            }
        }
    }
    for i := range accessible {
        if !accessible[i] {
            return false // 有房间无法进入
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func islandPerimeter(grid [][]int) int {
    res := 0
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == 1 { // 遇到陆地
                res += 4
                if j != len(grid[0])-1 && grid[i][j+1] == 1 {res -= 1} // 不是最后一列且右有陆地
                if i != len(grid)-1 && grid[i+1][j] == 1 {res -= 1} // 不是最后一排且下有陆地
                if i != 0 && grid[i-1][j] == 1 {res -= 1} // 不是第一排且上有陆地
                if j != 0 && grid[i][j-1] == 1 {res -= 1} // 不是第一列且左有陆地
            }
        }
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

var father []int

func validPath(n int, edges [][]int, source int, destination int) bool {
    father = make([]int, n)
    initial(n)
    for i := range edges {
        join(edges[i][0], edges[i][1])
    }
    return isSame(source, destination)
}

// 并查集初始化
func initial(n int) {
    for i := 0; i < n; i++ {
        father[i] = i
    }
}

// 并查集里寻根
func find(u int) int {
    if father[u] == u {
        return u
    }
    father[u] = find(father[u])
    return father[u]
}

// 判断a和b是否找到同一个根
func isSame(a int, b int) bool {
    a = find(a)
    b = find(b)
    return a == b
}

// 边a->b加入并差集
func join(a int, b int) {
    a = find(a)
    b = find(b)
    if a == b {
        return // 同根说明已经在一个集合里
    }
    father[a] = b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

var father []int
var n int

func findRedundantConnection(edges [][]int) []int {
    n = len(edges)
    father = make([]int, n+1)
    initial()
    for i := 0; i < n; i++ {
        if isSame(edges[i][0], edges[i][1]) {
            return edges[i]
        }
        join(edges[i][0], edges[i][1])
    }
    return []int{}
}
func initial() {
    for i := 0; i <= n; i++ {
        father[i] = i
    }
}
func isSame(a int, b int) bool {
    a = find(a)
    b = find(b)
    return a == b
}
func find(u int) int {
    if father[u] == u {
        return u
    }
    father[u] = find(father[u])
    return father[u]
}
func join(a int, b int) {
    a = find(a)
    b = find(b)
    if a == b {
        return
    }
    father[a] = b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

var father []int
var n int

func findRedundantDirectedConnection(edges [][]int) []int {
    inDegree := make([]int, len(edges)+1) // 记录各节点的入度
    for i := range edges {
        inDegree[edges[i][1]] += 1
    }
    twoDegree := make([]int, 0) // 记录入度为2的节点的两条边的索引
    for i := range edges {
        if inDegree[edges[i][1]] == 2 {
            twoDegree = append(twoDegree, i) // 找到入度为2的节点的一条边
        }
    }
    if len(twoDegree) != 0 {
        if isTreeAfterRemoveEdge(edges, twoDegree[1]) {
            return edges[twoDegree[1]] // 去掉数组中靠后的该边能构成树
        }
        return edges[twoDegree[0]] // 去掉数组中靠前的该边能构成树
    }
    return getRemoveEdge(edges)
}

// isTreeAfterRemoveEdge 判断删除一条边之后能否成树
func isTreeAfterRemoveEdge(edges [][]int, deleteEdgeIdx int) bool {
    n = len(edges)
    father = make([]int, n+1)
    initial()
    for i := range edges {
        if i == deleteEdgeIdx {
            continue // 不添加要删除的边
        }
        if isSame(edges[i][0], edges[i][1]) {
            return false // 该边加入会成环说明不能成树
        }
        join(edges[i][0], edges[i][1]) // 加入并查集
    }
    return true
}

// getRemoveEdge 找到加入后会成环的边
func getRemoveEdge(edges [][]int) []int {
    n = len(edges)
    father = make([]int, n+1)
    initial()
    for i := range edges {
        if isSame(edges[i][0], edges[i][1]) {
            return edges[i] // 找到加入后会成环的边
        }
        join(edges[i][0], edges[i][1]) // 加入并查集
    }
    return []int{}
}

// 并查集
func initial() {
    for i := 0; i <= n; i++ {
        father[i] = i
    }
}
func isSame(a int, b int) bool {
    a = find(a)
    b = find(b)
    return a == b
}
func find(u int) int {
    if father[u] == u {
        return u
    }
    father[u] = find(father[u])
    return father[u]
}
func join(a int, b int) {
    a = find(a)
    b = find(b)
    if a == b {
        return
    }
    father[a] = b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

package main

import (
    "fmt"
    "math"
)

func main() {
    // v是节点个数,e是边个数
    var v, e int
    fmt.Scan(&v, &e)

    // grid邻接矩阵保存图,权值初始化为10001,代表不相连
    grid := make([][]int, v+1)
    for i := range grid {
        grid[i] = make([]int, v+1)
        for j := range grid[i] {
            grid[i][j] = 10001
        }
    }

    // 填充grid
    var x, y, k int
    for ; e > 0; e-- {
        fmt.Scan(&x, &y, &k)
        grid[x][y] = k
        grid[y][x] = k
    }

    // Prim算法
    // 初始化minDist为10001
    minDist := make([]int, v+1)
    for i := range minDist {
        minDist[i] = 10001
    }
    // 记录节点是否在最小生成树中
    isInTree := make([]bool, v+1)

    // 从节点1开始加入minDist
    minDist[1] = 0

    // 遍历节点1~v-1
    for i := 1; i < v; i++ {
        // 初始化最近节点为-1,最近距离为最大整型
        cur := -1
        minVal := math.MaxInt32
        // 1. 遍历minDist找到离树的最近节点
        for j := 1; j <= v; j++ {
            // 判断节点是否不在树中且小于目前记录的最近距离
            if !isInTree[j] && minDist[j] < minVal {
                // 更新最近距离和节点
                minVal = minDist[j]
                cur = j
            }
        }

        // 2. 最近节点加入树
        isInTree[cur] = true

        // 3. 遍历节点,更新非树中各节点到树的最近距离
        for j := 1; j <= v; j++ {
            // 判断是否非树中节点且离刚新入树的节点距离小于minDist记录的距离
            if !isInTree[j] && grid[cur][j] < minDist[j] {
                // 更新minDist
                minDist[j] = grid[cur][j]
                // 记录边
                // parent[j] = cur
            }
        }
    }

    // 计算最小生成树的总权重
    result := 0
    // 遍历节点2~v
    for i := 2; i <= v; i++ {
        result += minDist[i]
    }
    fmt.Println(result)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

package main

import (
    "fmt"
    "sort"
)

// 边结构体，包含边的两个端点和边的权值
type Edge struct {
    From int
    To   int
    Cost int
}

// 并查集结构体
type UnionFind struct {
    parent []int
}

// 初始化并查集
func NewUnionFind(size int) *UnionFind {
    parent := make([]int, size)
    for i := range parent {
        parent[i] = i
    }
    return &UnionFind{parent}
}

// 查找根节点
func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x]) // 路径压缩
    }
    return uf.parent[x]
}

// 加入集合
func (uf *UnionFind) Union(x, y int) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    if rootX != rootY {
        uf.parent[rootY] = rootX
    }
}

func main() {
    // v是节点数,e是边数
    var v, e int
    fmt.Scan(&v, &e)

    // 获取各个边
    edges := make([]Edge, e)
    for i := 0; i < e; i++ {
        var v1, v2, val int
        fmt.Scan(&v1, &v2, &val)
        edges[i] = Edge{v1, v2, val}
    }

    // 按边的权值从小到大排序
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].Cost < edges[j].Cost
    })

    // 初始化并查集
    uf := NewUnionFind(v + 1)

    result := 0
    // 遍历边
    for _, edge := range edges {
        // 判断两个端点是否不在同一个集合中
        if uf.Find(edge.From) != uf.Find(edge.To) {
            // 计入结果集
            result += edge.Cost
            // 加入生成树中(入集)
            uf.Union(edge.From, edge.To)
            // 保存最小生成树的边
            // res_edge = append(res_edge, edge) 
        }
    }

    fmt.Println(result)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

package main

import (
    "fmt"
)

func main() {
    // n个点,m个依赖关系,t依赖s
    var n, m, s, t int
    fmt.Scan(&n, &m)

    // 记录每个文件的入度
    inDegree := make([]int, n)
    // 记录文件依赖关系
    umap := make(map[int][]int)
    result := make([]int, 0)

    for i := 0; i < m; i++ {
        fmt.Scan(&s, &t)
        // t的入度加一
        inDegree[t]++
        // 记录s->t
        umap[s] = append(umap[s], t)
    }

    queue := make([]int, 0)
    // 遍历节点入度
    for i := 0; i < n; i++ {
        if inDegree[i] == 0 {
            // 入度为0的节点作为开头加入队列
            queue = append(queue, i)
        }
    }

    for len(queue) > 0 {
        // 从队列中取出当前入度为0的点
        cur := queue[0]
        queue = queue[1:]
        result = append(result, cur)
        // 获取cur指向的点
        files := umap[cur]
        // 遍历cur指向的点
        for _, f := range files {
            // cur的指向的点入度-1
            inDegree[f]--
            // 判断该点入度是否为0
            if inDegree[f] == 0 {
                // 入度为0入队
                queue = append(queue, f)
            }
        }
    }
    // 判断结果集元素个数是否等于总节点数
    if len(result) == n {
        // 顺序打印拓扑排序序列
        for i := 0; i < n-1; i++ {
            fmt.Print(result[i], " ")
        }
        fmt.Println(result[n-1])
    } else {
        // 不是有向无环图,无法排序
        fmt.Println(-1)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

package main

import (
    "fmt"
    "math"
)

func main() {
    // n个节点m条边,p1->p2权值val
    var n, m, p1, p2, val int
    fmt.Scan(&n, &m)

    // 初始化邻接矩阵，用于存储边的权重
    grid := make([][]int, n+1)
    for i := range grid {
        grid[i] = make([]int, n+1)
        for j := range grid[i] {
            // 使用math.MaxInt32表示两点间无边
            grid[i][j] = math.MaxInt32 
        }
    }

    // 读入边信息并构建邻接矩阵
    for i := 0; i < m; i++ {
        fmt.Scan(&p1, &p2, &val)
        grid[p1][p2] = val
    }

    // 起点为节点1终点为节点n
    start := 1
    end := n

    // 存储从源点到每个节点的最短距离
    minDist := make([]int, n+1)
    for i := range minDist {
        // 初始化为无穷大
        minDist[i] = math.MaxInt32 
    }
    // 起始点到自身的距离为0
    minDist[start] = 0 

    // 记录点是否被访问过
    visited := make([]bool, n+1)

    // 遍历节点1-n
    for i := 1; i <= n; i++ {
        
        minVal := math.MaxInt32
        cur := 1

        // 遍历minDist选取距离源点最近且未访问过的节点
        for v := 1; v <= n; v++ {
            if !visited[v] && minDist[v] < minVal {
                minVal = minDist[v]
                cur = v
            }
        }

        // 标记该节点已被访问
        visited[cur] = true 

        // 更新非访问节点到源点的距离（即更新minDist数组）
        for v := 1; v <= n; v++ {
            if !visited[v] && grid[cur][v] != math.MaxInt32 && minDist[cur]+grid[cur][v] < minDist[v] {
                minDist[v] = minDist[cur] + grid[cur][v]
                // 记录边
                // parent[v] = cur; 
            }
        }
    }

    if minDist[end] == math.MaxInt32 {
        // 不能到达终点
        fmt.Println(-1) 
    } else {
        // 到达终点最短路径
        fmt.Println(minDist[end]) 
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105

package main

import (
    "container/heap"
    "fmt"
    "math"
)

// 定义边的结构体
type Edge struct {
    to  int
    val int
}

func main() {
    var n, m, p1, p2, val int
    fmt.Scan(&n, &m)

    // 初始化邻接表
    grid := make([][]Edge, n+1)

    // 读入边信息并构建邻接表
    for i := 0; i < m; i++ {
        fmt.Scan(&p1, &p2, &val)
        grid[p1] = append(grid[p1], Edge{p2, val})
    }

    start := 1
    end := n

    // 存储从源点到每个节点的最短距离
    minDist := make([]int, n+1)
    for i := range minDist {
        minDist[i] = math.MaxInt32 // 初始化为无穷大
    }
    minDist[start] = 0 // 起始点到自身的距离为0

    // 使用优先队列实现最小堆
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    heap.Push(&pq, &Item{value: start, priority: 0})

    // 记录顶点是否被访问过
    visited := make([]bool, n+1)

    for pq.Len() > 0 {
        // 从优先队列中取出当前距离起点最近的节点
        item := heap.Pop(&pq).(*Item)
        u := item.value

        if visited[u] {
            continue
        }
        visited[u] = true

        // 更新与当前节点相邻的节点的最短距离
        for _, edge := range grid[u] {
            v := edge.to
            w := edge.val

            if !visited[v] && minDist[u]+w < minDist[v] {
                minDist[v] = minDist[u] + w
                heap.Push(&pq, &Item{value: v, priority: minDist[v]})
            }
        }
    }

    // 输出结果
    if minDist[end] == math.MaxInt32 {
        fmt.Println(-1) // 不能到达终点
    } else {
        fmt.Println(minDist[end]) // 到达终点最短路径
    }
}

// 优先队列实现（最小堆）
type Item struct {
    value    int // 节点编号
    priority int // 源点到该节点的距离
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Item)
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}