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
44

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,b的根
    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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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) // 递归 向左探索
}
// 写法二：更通用
var dis = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func numIslands(grid [][]byte) int {
    res := 0
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == '1' {
                res++
                dfs(grid, i, j)
            }
        }
    }
    return res
}
func dfs(grid [][]byte, i, j int) {
    grid[i][j] = 'x'
    for _, offset := range dis {
        x := i + offset[0]
        y := j + offset[1]
        if x >= 0 && x < len(grid) && y >= 0 && y < len(grid[0]) && grid[x][y] == '1' {
            dfs(grid, 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
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
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

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) // 左
}
// 写法二：更通用
var dis = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var res int
var cnt int

func maxAreaOfIsland(grid [][]int) int {
    res = 0
    cnt = 0
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] == 1 {
                dfs(grid, i, j)
                res = max(res, cnt)
                cnt = 0
            }
        }
    } 
    return res
}

func dfs(grid [][]int, i, j int) {
    grid[i][j] = 0
    cnt++
    for _, offset := range dis {
        x := i + offset[0]
        y := j + offset[1]
        if x >= 0 && x < len(grid) && y >= 0 && y < len(grid[0]) && grid[x][y] == 1 {
            dfs(grid, 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
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
46
47
48

var visited [][][]bool

func pacificAtlantic(heights [][]int) [][]int {
	m := len(heights)
	n := len(heights[0])
	visited = make([][][]bool, m)
	for i := range visited {
		visited[i] = make([][]bool, n)
	}
	for i := range visited {
		for j := range visited[i] {
			visited[i][j] = make([]bool, 2)
		}
	}
	// 遍历首尾行，标记洋能到的区域
	for i := 0; i < n; i++ {
		dfs(heights, 0, i, 0)
		dfs(heights, m-1, i, 1)
	}
	// 遍历首尾列，标记洋能到的区域
	for i := 0; i < m; i++ {
		dfs(heights, i, 0, 0)
		dfs(heights, i, n-1, 1)
	}
	// 遍历矩阵，找两个洋都能到的
	res := [][]int{}
	for i := range heights {
		for j := range heights[i] {
			if visited[i][j][1] && visited[i][j][0] {
				res = append(res, []int{i, j})
			}
		}
	}
	return res
}

var dis = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

func dfs(heights [][]int, i, j, sign int) {
	visited[i][j][sign] = true
	for _, offset := range dis {
		x := i + offset[0]
		y := j + offset[1]
		if x >= 0 && x < len(heights) && y >= 0 && y < len(heights[0]) && heights[x][y] >= heights[i][j] && !visited[x][y][sign] {
			dfs(heights, x, y, 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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// 写法一
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
}
// 写法二
func canVisitAllRooms(rooms [][]int) bool {
    mp := make([]bool, len(rooms))
    mp[0] = true
    queue := []int{0}
    for len(queue) != 0 {
        for _, v := range rooms[queue[0]] {
            if !mp[v] {
                mp[v] = true
                queue = append(queue, v)
            }
        }
        queue = queue[1:]
    }
    for _, v := range mp {
        if !v {
            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

func validPath(n int, edges [][]int, source int, destination int) bool {
    // BFS
    if source == destination {
        return true
    }
    edgeMp := map[int][]int{}
    for _, edge := range edges {
        edgeMp[edge[0]] = append(edgeMp[edge[0]], edge[1])
        edgeMp[edge[1]] = append(edgeMp[edge[1]], edge[0])
    }
    mp := map[int]bool{}
    mp[source] = true
    queue := []int{source}
    for len(queue) != 0 {
        cur := queue[0]
        queue = queue[1:]
        for _, v := range edgeMp[cur] {
            if !mp[v] {
                if v == destination{
                    return true
                }
                mp[v] = true
                queue = append(queue, v)
            }
        }
    }
    return false
}

 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