图论-代码随想录刷题记录[JAVA]

文章目录

前言
深度优先搜索理论基础
所有可达路径
岛屿数量
岛屿最大面积
孤岛的总面积
沉没孤岛
水流问题
建造最大人工岛
字符串接龙
有向图的完全可达性
岛屿的周长
寻找存在的路径
冗余连接
冗余连接||
最小生成树之prim
kruskal算法
Floyd 算法
dijkstra（朴素版）

前言

新手小白记录第一次刷代码随想录
1.自用抽取精简的解题思路方便复盘
2.代码尽量多加注释
3.记录踩坑
4.边刷边记录，更有成就感！
5.解题思路绝大部分来自代码随想录【仅自用无商用！！！】

深度优先搜索理论基础

代码框架

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}

所有可达路径

【题目描述】

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

【输入描述】

第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

【输出描述】

输出所有的可达路径，路径中所有节点的后面跟一个空格，每条路径独占一行，存在多条路径，路径输出的顺序可任意。

如果不存在任何一条路径，则输出 -1。

注意输出的序列中，最后一个节点后面没有空格！例如正确的答案是 1 3 5,而不是 1 3 5， 5后面没有空格！

【输入示例】

5 5
1 3
3 5
1 2
2 4
4 5
【输出示例】

1 3 5
1 2 4 5

邻接矩阵

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {static List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径static List<Integer> path = new ArrayList<>(); // 1节点到终点的路径public static void dfs(int[][] graph, int x, int n) {// 当前遍历的节点x 到达节点nif (x == n) { // 找到符合条件的一条路径result.add(new ArrayList<>(path));return;}for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点if (graph[x][i] == 1) { // 找到 x链接的节点path.add(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.remove(path.size() - 1); // 回溯，撤销本节点}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();// 节点编号从1到n，所以申请 n+1 这么大的数组int[][] graph = new int[n + 1][n + 1];for (int i = 0; i < m; i++) {int s = scanner.nextInt();int t = scanner.nextInt();// 使用邻接矩阵表示无向图，1 表示 s 与 t 是相连的graph[s][t] = 1;}path.add(1); // 无论什么路径已经是从1节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.isEmpty()) System.out.println(-1);for (List<Integer> pa : result) {for (int i = 0; i < pa.size() - 1; i++) {System.out.print(pa.get(i) + " ");}System.out.println(pa.get(pa.size() - 1));}}
}

邻接表

import java.util.*;public class Main {static List<List<Integer>> res = new ArrayList<>();static List<Integer> path = new ArrayList<>();public static void dfs(List<LinkedList<Integer>> graph, int now, int n) {// 终止条件：找到一条从1到n的路径if (now == n) {res.add(new ArrayList<>(path));return;}// 遍历当前节点的所有邻接节点for (int i : graph.get(now)) {path.add(i);  // 添加当前节点到路径中dfs(graph, i, n);  // 递归探索下一节点path.remove(path.size() - 1);  // 回溯，移除当前节点}}public static void main(String args[]) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();  // 节点数int m = sc.nextInt();  // 边数// 初始化图的邻接表List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);for (int i = 0; i <= n; i++) {graph.add(new LinkedList<>());}// 构建图的邻接表int a, b;while (m-- > 0) {a = sc.nextInt();b = sc.nextInt();graph.get(a).add(b);  // 从a到b的边}// 从节点1开始路径搜索path.add(1);  // 初始路径包含节点1dfs(graph, 1, n);// 如果没有路径if (res.isEmpty()) {System.out.println(-1);  // 没有路径} else {// 打印所有路径for (List<Integer> re : res) {for (int i = 0; i < re.size() - 1; i++) {System.out.print(re.get(i) + " ");}System.out.println(re.get(re.size() - 1));  // 打印路径的最后一个节点}}}
}

岛屿数量

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例：

3
数据范围：

1 <= N, M <= 50

深搜版

import java.util.Scanner;public class Main {static int cnt = 0; // 用于计数岛屿数量static int direct[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向的移动// 深度优先搜索public static void dfs(int graph[][], int x, int y, boolean visited[][]) {// 遍历四个方向for (int i = 0; i < 4; i++) {int nextX = x + direct[i][0];  // 下一个位置的x坐标int nextY = y + direct[i][1];  // 下一个位置的y坐标// 判断是否越界if (nextX < 0 || nextY < 0 || nextX >= graph.length || nextY >= graph[0].length) {continue; // 如果越界，跳过}// 如果当前位置是陆地并且未访问过，递归搜索if (!visited[nextX][nextY] && graph[nextX][nextY] == 1) {visited[nextX][nextY] = true; // 标记为已访问dfs(graph, nextX, nextY, visited); // 递归搜索}}}public static void main(String[] args) {int n, m, a;Scanner sc = new Scanner(System.in);n = sc.nextInt(); // 行数m = sc.nextInt(); // 列数int[][] graph = new int[n][m]; // 地图boolean[][] visited = new boolean[n][m]; // 记录每个位置是否已访问// 读取地图for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {a = sc.nextInt();graph[i][j] = a; // 1表示陆地，0表示水域}}// 遍历整个图，每当找到一个未访问的陆地，执行深度优先搜索for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 找到一个未访问的陆地，开始深度优先搜索if (!visited[i][j] && graph[i][j] == 1) {cnt++; // 找到一个岛屿visited[i][j] = true; // 标记为已访问dfs(graph, i, j, visited); // 递归搜索整个岛屿}}}// 输出岛屿的数量System.out.println(cnt);}
}

另一种写终止条件的写法

public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {// 终止条件：访问过的节点 或者 遇到海水（grid[x][y] == 0）if (visited[x][y] || grid[x][y] == 0) {return;}visited[x][y] = true; // 标记当前位置为已访问// 遍历四个方向for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];// 检查是否越界if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}// 递归调用 DFSdfs(grid, visited, nextX, nextY);}}

广搜版

不少同学用广搜做这道题目的时候，超时了。这里有一个广搜中很重要的细节：
根本原因是只要加入队列就代表走过，就需要标记，而不是从队列拿出来的时候再去标记走过。
很多同学可能感觉这有区别吗？
如果从队列拿出节点，再去标记这个节点走过，就会发生下图所示的结果，会导致很多节点重复加入队列。

在这里插入图片描述

import java.util.*;public class Main {// 定义四个方向的偏移量：下、右、上、左public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 下右上左// 自定义pair类，用于存储坐标static class pair {int first, second;pair(int x, int y) {this.first = x;this.second = y;}}// BFS遍历函数public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {Queue<pair> queue = new LinkedList<pair>();  // 定义坐标队列queue.add(new pair(x, y)); // 入队当前坐标visited[x][y] = true; // 标记当前位置为已访问while (!queue.isEmpty()) {int curX = queue.peek().first;  // 获取队列头的X坐标int curY = queue.poll().second; // 获取队列头的Y坐标并出队（poll是把对头元素出队了）// 遍历四个方向for (int i = 0; i < 4; i++) {// 计算下一个坐标int nextX = curX + dir[i][0];int nextY = curY + dir[i][1];// 检查越界if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}// 如果没有访问过并且该点是陆地（值为1），则入队if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {queue.add(new pair(nextX, nextY));visited[nextX][nextY] = true; // 标记为已访问}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入网格的行数和列数int m = sc.nextInt();int n = sc.nextInt();int[][] grid = new int[m][n];boolean[][] visited = new boolean[m][n];int ans = 0;// 输入网格的每个值（0为水域，1为陆地）for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}// 遍历网格，查找所有的岛屿for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 如果该点是陆地并且未访问过，则说明发现一个新的岛屿if (!visited[i][j] && grid[i][j] == 1) {ans++; // 岛屿数量加一bfs(grid, visited, i, j); // 通过BFS将该岛屿所有的陆地标记为已访问}}}// 输出岛屿数量System.out.println(ans);}
}

岛屿最大面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例

写在前面

count是类成员变量，如果不加 static，它们将被视为实例变量，只有通过实例化 Main 类才能访问它们。
bfs 方法是静态方法，它可以直接通过类名 Main.bfs() 调用。如果不将其设为 static，它就需要依赖于一个 Main 类的实例来调用。
如果不加 static，访问count 以及调用 bfs 会出现问题，因为：count 是实例变量，而 bfs 是静态方法。静态方法只能访问静态变量和静态方法。
即使你没有实例化 Main 类，你也希望在 main 方法中访问它们，这就要求count 也必须是静态的。

dfs

写法一，dfs只处理下一个节点，即在主函数遇到岛屿就计数为1，dfs处理接下来的相邻陆地

import java.util.*;public class Main {// 定义四个方向的偏移量：右、下、左、上public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};static int count; // 记录每次DFS访问的陆地数量// 深度优先搜索 (DFS) 函数public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];// 检查越界if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}// 如果该位置没有访问过且是陆地，则继续DFSif (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;count++; // 增加当前岛屿的陆地数量dfs(grid, visited, nextX, nextY); // 递归访问相邻的陆地}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入网格的行数n和列数mint n = sc.nextInt();int m = sc.nextInt();// 创建网格并填充输入数据int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = sc.nextInt();}}// 创建一个visited数组，用来标记访问过的位置boolean[][] visited = new boolean[n][m];int result = 0; // 最终记录最大岛屿面积// 遍历每一个格子for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果当前格子是陆地并且未被访问过，进行DFSif (!visited[i][j] && grid[i][j] == 1) {count = 1;  // 这里遇到陆地了，先计数1visited[i][j] = true;dfs(grid, visited, i, j); // 递归访问与当前陆地相连的陆地result = Math.max(result, count); // 更新最大岛屿面积}}}// 输出结果System.out.println(result);}
}

写法二，dfs处理当前节点，即在主函数遇到岛屿就计数为0，dfs处理接下来的全部陆地

// 版本二
import java.util.Scanner;public class Main {// 定义四个方向的偏移量：右、下、左、上public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};static int count; // 记录每次DFS访问的陆地数量// 深度优先搜索 (DFS) 函数public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {// 终止条件：访问过的节点 或者 遇到海水if (visited[x][y] || grid[x][y] == 0) return;visited[x][y] = true; // 标记当前位置为已访问count++; // 每访问到一个陆地，计数+1// 遍历四个方向for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];// 检查越界if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}// 递归调用 DFSdfs(grid, visited, nextX, nextY);}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入网格的行数n和列数mint n = sc.nextInt();int m = sc.nextInt();// 创建网格并填充输入数据int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = sc.nextInt();}}// 创建一个visited数组，用来标记访问过的位置boolean[][] visited = new boolean[n][m];int result = 0; // 最终记录最大岛屿面积// 遍历每一个格子for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果当前格子是陆地并且未被访问过，进行DFSif (!visited[i][j] && grid[i][j] == 1) {count = 0;  // 遇到陆地时先计数为0，进入DFS后开始从1计数dfs(grid, visited, i, j); // 递归访问与当前陆地相连的陆地result = Math.max(result, count); // 更新最大岛屿面积}}}// 输出结果System.out.println(result);}
}

大家通过注释可以发现，两种写法，版本一，在主函数遇到陆地就计数为1，接下来的相邻陆地都在dfs中计算。

版本二在主函数遇到陆地计数为0，也就是不计数，陆地数量都去dfs里做计算。

bfs的代码省略

孤岛的总面积

目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例：


import java.util.*;public class Main {private static int count = 0;private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向private static void bfs(int[][] grid, int x, int y) {Queue<int[]> que = new LinkedList<>();que.add(new int[]{x, y});grid[x][y] = 0; // 只要加入队列，立刻标记count++;while (!que.isEmpty()) {int[] cur = que.poll();int curx = cur[0];int cury = cur[1];for (int i = 0; i < 4; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue; // 越界了，直接跳过if (grid[nextx][nexty] == 1) {que.add(new int[]{nextx, nexty});count++;grid[nextx][nexty] = 0; // 只要加入队列立刻标记}}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] grid = new int[n][m];// 读取网格for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scanner.nextInt();}}// 从左侧边，和右侧边向中间遍历for (int 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 (int 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 = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) bfs(grid, i, j);}}System.out.println(count);}
}

沉没孤岛

题目描述：

现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出将孤岛“沉没”之后的岛屿矩阵。

输入示例：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例：

1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1

思路
1.从边界遍历把接壤陆地的岛屿标记为2
2. 再遍历一遍把孤岛变为0
3. 最后再遍历一遍把孤岛变为2

import java.util.Scanner;public class Main{static int[][] dir = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} }; // 保存四个方向public static int n,m;public static void dfs(int grid[][],int x,int y){grid[x][y]=2;for(int i=0;i<4;i++){int nextX=x+dir[i][0];int nextY=y+dir[i][1];if(nextY<0||nextY>=m||nextX<0||nextX>=n) continue;//这里是continue 不是returnif (grid[nextX][nextY] == 0 || grid[nextX][nextY] == 2) continue;dfs(grid,nextX,nextY);}}    public static void main (String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scanner.nextInt();}}//从左右向中间便利 把半岛变为2for(int i=0;i<n;i++){if(grid[i][0]==1) dfs(grid,i,0);if(grid[i][m-1]==1) dfs(grid,i,m-1);}//从上下 向中间便利 把半岛变为2for(int i=0;i<m;i++){if(grid[0][i]==1) dfs(grid,0,i);if(grid[n-1][i]==1) dfs(grid,n-1,i);}//把孤岛变为0 把半岛变回1for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1) grid[i][j]=0;if(grid[i][j]==2) grid[i][j]=1;System.out.print(grid[i][j] + " ");}System.out.println();}scanner.close();}
}

水流问题

【题目描述】：

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

【输入描述】：

第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。

后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。

【输出描述】：

输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。

【输入示例】：

5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1
【输出示例】：

0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1
【提示信息】：

在这里插入图片描述

图中的蓝色方块上的雨水既能流向第一组边界，也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。

【数据范围】：

1 <= M, N <= 50

思路
那么我们可以反过来想，从第一组边界上的节点逆流而上，将遍历过的节点都标记上。

同样从第二组边界的边上节点逆流而上，将遍历过的节点也标记上。

然后两方都标记过的节点就是所求。

import java.util.Scanner;public class Main {// 定义四个方向public static int[][] dir = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };// DFS搜索函数public static void dfs(int[][] heights, int x, int y, boolean[][] visited) {// 如果已经访问过，则返回if (visited[x][y]) return;// 标记为已访问visited[x][y] = true;// 遍历四个方向for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];// 判断边界if (nextx < 0 || nextx >= heights.length || nexty < 0 || nexty >= heights[0].length) continue;// 判断是否可以流动（水只能从低向高流动）if (heights[x][y] > heights[nextx][nexty]) continue;// 递归调用DFSdfs(heights, nextx, nexty, visited);}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();  // 行数int n = sc.nextInt();  // 列数// 读取矩阵int[][] heights = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {heights[i][j] = sc.nextInt();}}// 初始化两个boolean数组，代表两个边界boolean[][] border1 = new boolean[m][n]; // 第一个边界boolean[][] border2 = new boolean[m][n]; // 第二个边界// 从上下边界开始DFSfor (int i = 0; i < n; i++) {dfs(heights, 0, i, border1);    // 从上边界开始dfs(heights, m - 1, i, border2); // 从下边界开始}// 从左右边界开始DFSfor (int i = 0; i < m; i++) {dfs(heights, i, 0, border1);     // 从左边界开始dfs(heights, i, n - 1, border2); // 从右边界开始}// 输出符合条件的坐标for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 如果该位置能同时从两个边界到达if (border1[i][j] && border2[i][j]) {System.out.println(i + " " + j);}}}sc.close();}
}

建造最大人工岛

【题目描述】：

给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。

岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。

【输入描述】：

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

【输出描述】：

输出一个整数，表示最大的岛屿面积。

【输入示例】：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

【输出示例】

思路

用Map来记录岛屿的面积，key为岛屿编号，value为岛屿面积。
然后再遍历一遍海洋，比较当哪一块海洋变为陆地的时候，周边相邻的岛屿面积最大。

public class Main {// 该方法采用 DFS// 定义全局变量// 记录每次每个岛屿的面积static int count;// 对每个岛屿进行标记static int mark;// 定义二维数组表示四个方位static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};// DFS 进行搜索，将每个岛屿标记为不同的数字public static void dfs(int[][] grid, int x, int y, boolean[][] visited) {// 当遇到边界，直接returnif (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return;// 遇到已经访问过的或者遇到海水，直接返回if (visited[x][y] || grid[x][y] == 0) return;visited[x][y] = true;count++;grid[x][y] = mark;// 继续向下层搜索dfs(grid, x, y + 1, visited);dfs(grid, x, y - 1, visited);dfs(grid, x + 1, y, visited);dfs(grid, x - 1, y, visited);}public static void main (String[] args) {// 接收输入Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[][] grid = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}// 初始化mark变量，从2开始（区别于0水，1岛屿）mark = 2;// 定义二位boolean数组记录该位置是否被访问boolean[][] visited = new boolean[m][n];// 定义一个HashMap，记录某片岛屿的标记号和面积HashMap<Integer, Integer> getSize = new HashMap<>();// 定义一个HashSet，用来判断某一位置水四周是否存在不同标记编号的岛屿HashSet<Integer> set = new HashSet<>();// 定义一个boolean变量，看看DFS之后，是否全是岛屿boolean isAllIsland = true;// 遍历二维数组进行DFS搜索，标记每片岛屿的编号，记录对应的面积for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) isAllIsland = false;if (grid[i][j] == 1) {count = 0;dfs(grid, i, j, visited);getSize.put(mark, count);mark++;}}}int result = 0;if (isAllIsland) result =  m * n;// 对标记完的grid继续遍历，判断每个水位置四周是否有岛屿，并记录下四周不同相邻岛屿面积之和// 每次计算完一个水位置周围可能存在的岛屿面积之和，更新下result变量for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {set.clear();// 当前水位置变更为岛屿，所以初始化为1int curSize = 1;for (int[] dir : dirs) {int curRow = i + dir[0];int curCol = j + dir[1];if (curRow < 0 || curRow >= m || curCol < 0 || curCol >= n) continue;int curMark = grid[curRow][curCol];// 如果当前相邻的岛屿已经遍历过或者HashMap中不存在这个编号，继续搜索if (set.contains(curMark) || !getSize.containsKey(curMark)) continue;set.add(curMark);curSize += getSize.get(curMark);}result = Math.max(result, curSize);}}}// 打印结果System.out.println(result);}
}

字符串接龙

【题目描述】

字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列：

序列中第一个字符串是 beginStr。

序列中最后一个字符串是 endStr。

每次转换只能改变一个字符。

转换过程中的中间字符串必须是字典 strList 中的字符串。

给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。

【输入描述】

第一行包含一个整数 N，表示字典 strList 中的字符串数量。第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。后续 N 行，每行一个字符串，代表 strList 中的字符串。

【输出描述】

输出一个整数，代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列，则输出 0。

【输入示例】

6
abc def
efc
dbc
ebc
dec
dfc
yhn

【输出示例】

提示信息

从 startStr 到 endStr，在 strList 中最短的路径为 abc -> dbc -> dec -> def，所以输出结果为 4

数据范围：

2 <= N <= 500

思路

以示例1为例，从这个图中可以看出 abc 到 def的路线不止一条，但最短的一条路径上是4个节点。

在这里插入图片描述
本题只需要求出最短路径的长度就可以了，不用找出具体路径。

所以这道题要解决两个问题：

图中的线是如何连在一起的
起点和终点的最短路径长度
首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个。

所以判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。

然后就是求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。

本题如果用深搜，会比较麻烦，要在到达终点的不同路径中选则一条最短路。而广搜只要达到终点，一定是最短路。

广搜的逐层扩展特性

BFS 从起点开始，将所有与起点直接相连的节点加入到第一层队列，然后从第一层队列中的节点依次扩展到下一层。
换句话说，BFS 按距离的顺序逐层扩展：先处理与起点距离为 1 的节点，然后是距离为 2 的节点，依此类推。

最先访问到某节点时路径必然最短

对于无权图，每条边的代价是相同的（等于 1）。因此，从起点扩展到某个节点的路径长度直接对应 BFS 的层数。
当 BFS 搜索到某个节点时，这是第一次到达该节点，且此时路径长度必然是最短的。
一旦到达终点（目标节点），BFS 会立即返回路径长度，因为广搜的特性保证了这是首次到达终点，也即最短路径。

与深搜的对比

深度优先搜索（DFS）沿着一条路径深入探索，可能需要遍历完整张图后才能找到所有路径，然后再从中比较出最短路径。

注意：
本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！（visitMap 可以同时记录路径长度）
使用set来检查字符串是否出现在字符串集合里更快一些

import java.util.*;
public class Main {public static int ladderLength(String beginWord,String endWord,List<String>strList){//用ste来查询你换的每个字符串在不在字典strList中HashSet<String> set = new HashSet<>(strList);//bfs所以需要一个队列//存储每次变更一个字符得到的且存在容器中的新字符Queue<String> queue = new LinkedList<>();//用hashMap存储遍历到的字符串以及所走过的路径HashMap<String,Integer> visitMap = new HashMap<>();queue.offer(beginWord);visitMap.put(beginWord,1);while(!queue.isEmpty()){String curWord = queue.poll();int path=visitMap.get(curWord);for(int i=0;i<curWord.length();i++){char[] ch =curWord.toCharArray();//每个位置尝试26个字母for(char k ='a';k<='z';k++){ch[i]=k;String newWord=new String(ch);if(newWord.equals(endWord)) return path+1;//如果这个字符 存在于strLust字典中//并且还没有被访问到if(set.contains(newWord)&&!visitMap.containsKey(newWord)){visitMap.put(newWord,path+1);queue.offer(newWord);}}}}return 0;}public static void main (String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();sc.nextLine(); //接收的是换行符？String[] strs = sc.nextLine().split(" "); //放入beginStr 和 endStrList<String> strList = new ArrayList<>();//输入字典strListfor (int i = 0; i < N; i++) {strList.add(sc.nextLine());}int result = ladderLength(strs[0], strs[1], strList);System.out.println(result);}
}

有向图的完全可达性

【题目描述】

给定一个有向图，包含 N 个节点，节点编号分别为 1，2，…，N。现从 1 号节点开始，如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

【输入描述】

第一行包含两个正整数，表示节点数量 N 和边的数量 K。后续 K 行，每行两个正整数 s 和 t，表示从 s 节点有一条边单向连接到 t 节点。

【输出描述】

如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

【输入示例】

4 4
1 2
2 1
1 3
2 4
【输出示例】

思路
所以本题是一个有向图搜索全路径的问题。只能用深搜（DFS）或者广搜（BFS）来搜。

用邻接矩阵还是邻接表？
邻接表。因为邻接表可以直观地表示每个节点的出边集合。

以下dfs分析大家一定要仔细看，本题有两种dfs的解法。
深搜三部曲：

1.确认递归函数，参数

需要传入地图，需要知道当前我们拿到的key，以至于去下一个房间。

同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。

所以递归函数参数如下：

// key 当前得到的可以 
// visited 记录访问过的房间 
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {

2.确认终止条件

遍历的时候，什么时候终止呢？

这里有一个很重要的逻辑，就是在递归中，我们是处理当前访问的节点，还是处理下一个要访问的节点。

这决定终止条件怎么写。

首先明确，本题中什么叫做处理，就是 visited数组来记录访问过的节点，该节点默认数组里元素都是false，把元素标记为true就是处理本节点了。

如果我们是处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。
代码就是这样：

写法一：处理当前访问的节点
在处理当前节点时标记为已访问：

import java.util.*;public class Main {public static void dfs(List<List<Integer>> graph, int key, boolean[] visited) {if (visited[key]) {return;}visited[key] = true; // 标记当前节点已访问List<Integer> neighbors = graph.get(key);for (int neighbor : neighbors) {dfs(graph, neighbor, visited); // 继续递归}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 节点数int m = scanner.nextInt(); // 边数List<List<Integer>> graph = new ArrayList<>();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}for (int i = 0; i < m; i++) {int s = scanner.nextInt();int t = scanner.nextInt();graph.get(s).add(t); // 构建邻接表}boolean[] visited = new boolean[n + 1];dfs(graph, 1, visited);for (int i = 1; i <= n; i++) {if (!visited[i]) {System.out.println(-1);return;}}System.out.println(1);}
}

写法二：处理下一个要访问的节点
在遍历当前节点的邻接节点时直接判断并标记下一个节点：

import java.util.*;public class Main {public static void dfs(List<List<Integer>> graph, int key, boolean[] visited) {List<Integer> neighbors = graph.get(key);for (int neighbor : neighbors) {if (!visited[neighbor]) { // 如果未访问visited[neighbor] = true; // 立即标记dfs(graph, neighbor, visited); // 继续递归}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 节点数int m = scanner.nextInt(); // 边数List<List<Integer>> graph = new ArrayList<>();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}for (int i = 0; i < m; i++) {int s = scanner.nextInt();int t = scanner.nextInt();graph.get(s).add(t); // 构建邻接表}boolean[] visited = new boolean[n + 1];visited[1] = true; // 预先标记起点为访问dfs(graph, 1, visited);for (int i = 1; i <= n; i++) {if (!visited[i]) {System.out.println(-1);return;}}System.out.println(1);}
}

可以看出，如何看待我们要访问的节点，直接决定了两种不一样的写法，很多录友对这一块很模糊，可能做过这道题，但没有思考到这个维度上。

处理目前搜索节点出发的路径
其实在上面，深搜三部曲第二部，就已经讲了，因为终止条件的两种写法，直接决定了两种不一样的递归写法。

这里还有细节：

看上面两个版本的写法中，好像没有发现回溯的逻辑。

我们都知道，有递归就有回溯，回溯就在递归函数的下面，那么之前我们做的dfs题目，都需要回溯操作，为什么本题就没有回溯呢？

代码中可以看到dfs函数下面并没有回溯的操作。

此时就要在思考本题的要求了，本题是需要判断 1节点是否能到所有节点，那么我们就没有必要回溯去撤销操作了，只要遍历过的节点一律都标记上。

那什么时候需要回溯操作呢？

当我们需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”，如果不理解的话，去看我写的 0098.所有可达路径的题解。

import java.util.*;public class Main {public static List<List<Integer>> adjList = new ArrayList<>();// 深度优先搜索public static void dfs(boolean[] visited, int key) {if (visited[key]) return;visited[key] = true;List<Integer> neighbors = adjList.get(key);for (int neighbor : neighbors) {dfs(visited, neighbor);}}// 广度优先搜索public static void bfs(boolean[] visited, int key) {Queue<Integer> que = new LinkedList<>(); // 注意正确实例化 Queueque.add(key);visited[key] = true;while (!que.isEmpty()) {int now = que.poll();List<Integer> neighbors = adjList.get(now);for (int neighbor : neighbors) {if (!visited[neighbor]) {visited[neighbor] = true;que.add(neighbor);}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int vertices_num = sc.nextInt(); // 节点数量int line_num = sc.nextInt();     // 边数量// 初始化邻接表for (int i = 0; i <= vertices_num; i++) { // 节点编号从 1 开始，预留 0 位置adjList.add(new LinkedList<>());}// 构造邻接表for (int i = 0; i < line_num; i++) {int s = sc.nextInt();int t = sc.nextInt();adjList.get(s).add(t);}// 检查连通性boolean[] visited = new boolean[vertices_num + 1];// bfs(visited, 1); // 可以切换为 dfs(visited, 1);// 判断所有节点是否可达for (int i = 1; i <= vertices_num; i++) { // 从 1 开始检查if (!visited[i]) {System.out.println(-1);return;}}System.out.println(1);}
}

岛屿的周长

【题目描述】

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。

你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿，假设组成岛屿的陆地边长都为 1，请计算岛屿的周长。岛屿内部没有水域。

【输入描述】

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

【输出描述】

输出一个整数，表示岛屿的周长。

【输入示例】

5 5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
【输出示例】

思路
岛屿问题最容易让人想到BFS或者DFS，但本题确实还用不上。

遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。

如果该陆地上下左右的空格是有水域，则说明是一条边，如图：

import java.util.*;public class Main {// 每次遍历到1，探索其周围4个方向，并记录周长，最终合计// 声明全局变量，dirs表示4个方向static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};// 统计每单个1的周长static int count;// 探索其周围4个方向，并记录周长public static void helper(int[][] grid, int x, int y) {for (int[] dir : dirs) {int nx = x + dir[0];int ny = y + dir[1];// 遇到边界或者水，周长加一if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length|| grid[nx][ny] == 0) {count++;}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 接收输入int M = sc.nextInt();int N = sc.nextInt();int[][] grid = new int[M][N];for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {grid[i][j] = sc.nextInt();}}int result = 0; // 总周长for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (grid[i][j] == 1) {count = 0;helper(grid, i, j);// 更新总周长result += count;}}}// 打印结果System.out.println(result);}
}

寻找存在的路径

【题目描述】

给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。

你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。

【输入描述】

第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。

后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。

最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。

【输出描述】

输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。

【输入示例】

5 4
1 2
1 3
2 4
3 4
1 4
【输出示例】

import java.util.*;public class Main {public static void main(String[] args) {int N, M;Scanner scanner = new Scanner(System.in);N = scanner.nextInt();M = scanner.nextInt();DisJoint disJoint = new DisJoint(N + 1);for (int i = 0; i < M; ++i) {disJoint.join(scanner.nextInt(), scanner.nextInt());}if(disJoint.isSame(scanner.nextInt(), scanner.nextInt())) {System.out.println("1");} else {System.out.println("0");}}
}// 并查集模板
class DisJoint {private int[] parent;// 构造函数public DisJoint(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i; // 初始化时每个元素的父节点是自己}}// 查找根节点，并做路径压缩public int find(int n) {if (parent[n] != n) {parent[n] = find(parent[n]); // 路径压缩}return parent[n];}// 判断两个元素是否在同一集合public boolean isSame(int n, int m) {return find(n) == find(m); // 如果根节点相同，则属于同一集合}// 合并两个集合public void join(int n, int m) {int rootN = find(n);int rootM = find(m);if (rootN != rootM) {parent[rootN] = rootM; // 将rootN的根节点连接到rootM}}
}

冗余连接

题目描述

有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：

在这里插入图片描述

现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图

在这里插入图片描述

先请你找出冗余边，删除后，使该图可以重新变成一棵树。

输入描述

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

输入示例

3
1 2
2 3
1 3
输出示例

1 3

图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3

思路
那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。

如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。

题目要求 “请删除标准输入中最后出现的那条边” ，这代码分明是遇到在同一个根的两个节点立刻就返回了，怎么就求出最后出现的那条边了呢。

有这种疑惑的录友是认为发现一条冗余边后，后面还可能会有一条冗余边。其实并不会。

题目是在树的基础上添加一条边，所以冗余边仅仅是一条。到这一条可能靠前出现，可能靠后出现。

import java.util.*;public class Main {public static void main(String[] args) {int N, M;Scanner scanner = new Scanner(System.in);N = scanner.nextInt();DisJoint disJoint = new DisJoint(N + 1);for (int i = 0; i < N; ++i) {int a = scanner.nextInt();int b = scanner.nextInt();if(disJoint.isSame(a,b)){System.out.println(a+" "+b);}disJoint.join(a,b);}scanner.close();}
}// 并查集模板
class DisJoint {private int[] parent;// 构造函数public DisJoint(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i; // 初始化时每个元素的父节点是自己}}// 查找根节点，并做路径压缩public int find(int n) {if (parent[n] != n) {parent[n] = find(parent[n]); // 路径压缩}return parent[n];}// 判断两个元素是否在同一集合public boolean isSame(int n, int m) {return find(n) == find(m); // 如果根节点相同，则属于同一集合}// 合并两个集合public void join(int n, int m) {int rootN = find(n);int rootM = find(m);if (rootN != rootM) {parent[rootN] = rootM; // 将rootN的根节点连接到rootM}}
}

冗余连接||

有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：

在这里插入图片描述
现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。

在这里插入图片描述
输入一个有向图，该图由一个有着 n 个节点(节点编号从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N，表示有向图中节点和边的个数。

后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边

输出描述

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

输入示例

3
1 2
1 3
2 3
输出示例

2 3

思路
本题的本质是：有一个有向图，是由一颗有向树 + 一条有向边组成的（所以此时这个图就不能称之为有向树），现在让我们找到那条边把这条边删了，让这个图恢复为有向树。
还有“若有多条边可以删除，请输出标准输入中最后出现的一条边”，这说明在两条边都可以删除的情况下，要删顺序靠后的边！

我们来想一下有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）。

所以情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了
在这里插入图片描述
找到了节点3 的入度为2，删 1 -> 3 或者 2 -> 3 。选择删顺序靠后便可。

但入度为2 还有一种情况，情况二，只能删特定的一条边，如图：

在这里插入图片描述
节点3 的入度为 2，但在删除边的时候，只能删这条边（节点1 -> 节点3），如果删这条边（节点4 -> 节点3），那么删后本图也不是有向树了（因为找不到根节点）。

综上，如果发现入度为2的节点，我们需要判断删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。

情况三：如果没有入度为2的点，说明图中有环了（注意是有向环）。

在这里插入图片描述
对于情况三，删掉构成环的边就可以了。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {static int n;static int[] father = new int[1001]; // 并查集数组// 并查集初始化public static void init() {for (int i = 1; i <= n; ++i) {father[i] = i;}}// 并查集里寻根的过程public static int find(int u) {if (u == father[u]) return u;return father[u] = find(father[u]); // 路径压缩}// 将 v->u 这条边加入并查集public static void join(int u, int v) {u = find(u);v = find(v);if (u != v) {father[v] = u; // 合并两棵树}}// 判断 u 和 v 是否有同一个根public static boolean same(int u, int v) {return find(u) == find(v);}// 在有向图里找到删除的那条边，使其变成树public static void getRemoveEdge(List<int[]> edges) {init(); // 初始化并查集for (int i = 0; i < n; i++) { // 遍历所有的边if (same(edges.get(i)[0], edges.get(i)[1])) { // 如果构成有向环了，就是要删除的边System.out.println(edges.get(i)[0] + " " + edges.get(i)[1]);return;} else {join(edges.get(i)[0], edges.get(i)[1]);}}}// 删一条边之后判断是不是树public static boolean isTreeAfterRemoveEdge(List<int[]> edges, int deleteEdge) {init(); // 初始化并查集for (int i = 0; i < n; i++) {if (i == deleteEdge) continue;if (same(edges.get(i)[0], edges.get(i)[1])) { // 如果构成有向环了，一定不是树return false;}join(edges.get(i)[0], edges.get(i)[1]);}return true;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);List<int[]> edges = new ArrayList<>(); // 存储所有的边n = sc.nextInt(); // 顶点数int[] inDegree = new int[n + 1]; // 记录每个节点的入度for (int i = 0; i < n; i++) {int s = sc.nextInt(); // 边的起点int t = sc.nextInt(); // 边的终点inDegree[t]++;edges.add(new int[]{s, t}); // 将边加入列表}List<Integer> vec = new ArrayList<>(); // 记录入度为2的边（如果有的话就两条边）// 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边for (int i = n - 1; i >= 0; i--) {if (inDegree[edges.get(i)[1]] == 2) {vec.add(i);}}// 情况一、情况二if (vec.size() > 0) {// vec里的边已经按照倒叙放的，所以优先删 vec.get(0) 这条边if (isTreeAfterRemoveEdge(edges, vec.get(0))) {System.out.println(edges.get(vec.get(0))[0] + " " + edges.get(vec.get(0))[1]);} else {System.out.println(edges.get(vec.get(1))[0] + " " + edges.get(vec.get(1))[1]);}return;}// 处理情况三：明确没有入度为2的情况，一定有有向环，找到构成环的边返回即可getRemoveEdge(edges);}
}

最小生成树之prim

卡码网：53.寻宝

题目描述：

在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将所有岛屿联通起来。

给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。

输入描述：

第一行包含两个整数V 和 E，V代表顶点数，E代表边数。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。

接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。

输出描述：

输出联通所有岛屿的最小路径总距离

输入示例：

7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1
输出示例：

思路

第一步，选距离生成树最近节点
第二步，最近节点加入生成树
第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
minDist数组用来记录每一个节点距离最小生成树的最近距离。
示例中节点编号是从1开始，minDist数组下标也从 1 开始计数。

初始状态

minDist 数组里的数值初始化为最大数，因为本题节点距离不会超过 10000，所以初始化最大数为 10001就可以。

现在还没有最小生成树，默认每个节点距离最小生成树是最大的，这样后面我们在比较的时候，发现更近的距离，才能更新到 minDist 数组上。
在这里插入图片描述

模拟过程（只模拟两轮）

第一轮

1、prim三部曲，第一步：选距离生成树最近节点

选择距离最小生成树最近的节点，加入到最小生成树，刚开始还没有最小生成树，所以随便选一个节点加入就好（因为每一个节点一定会在最小生成树里，所以随便选一个就好），那我们选择节点1 （符合遍历数组的习惯，第一个遍历的也是节点1）

2、prim三部曲，第二步：最近节点加入生成树

此时节点1 已经算最小生成树的节点。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

在这里插入图片描述
注意图中我标记了 minDist数组里更新的权值，是哪两个节点之间的权值，例如 minDist[2] =1 ，这个 1 是节点1 与节点2 之间的连线，清楚这一点对最后我们记录最小生成树的权值总和很重要。

第二轮
1、prim三部曲，第一步：选距离生成树最近节点

选取一个距离最小生成树（节点1）最近的非生成树里的节点，节点2，3，5 距离最小生成树（节点1）最近，选节点 2（其实选节点3或者节点2都可以，距离一样的）加入最小生成树。

2、prim三部曲，第二步：最近节点加入生成树

此时节点1 和节点2，已经是最小生成树的节点。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

接下来，我们要更新节点距离最小生成树的距离，如图：
在这里插入图片描述

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int v = scanner.nextInt();int e = scanner.nextInt();// 初始化邻接矩阵，所有值初始化为一个大值，表示无穷大int[][] grid = new int[v + 1][v + 1];for (int i = 1; i <= v; i++) {Arrays.fill(grid[i], 10001);}// 读取边的信息并填充邻接矩阵for (int i = 0; i < e; i++) {int x = scanner.nextInt();int y = scanner.nextInt();int k = scanner.nextInt();grid[x][y] = k;grid[y][x] = k;}// 所有节点到最小生成树的最小距离int[] minDist = new int[v + 1];Arrays.fill(minDist, 10001);// 记录节点是否在树里boolean[] isInTree = new boolean[v + 1];// Prim算法主循环 只需要循环v-1次建立v-1条边for (int i = 1; i < v; i++) {int cur = -1;// 用于记录距离生成树最近的节点int minVal = Integer.MAX_VALUE; // 记录最短距离// 选择距离生成树最近的节点for (int j = 1; j <= v; j++) {// 如果这个点不在生成树里面，且它的距离小于当前最小值if (!isInTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}// 将最近的节点加入生成树isInTree[cur] = true;// 更新非生成树节点到生成树的距离for (int j = 1; j <= v; j++) {//当前cur节点比较if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}// 统计结果int result = 0;for (int i = 2; i <= v; i++) {result += minDist[i];// 从2开始，跳过起始节点}System.out.println(result);scanner.close();}
}

kruskal算法

题目同上题，找最小生成树。

思路

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
边的权值排序，因为要优先选最小的边加入到生成树里
遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

模拟
在这里插入图片描述
排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]

(1,2) 表示节点1 与节点2 之间的边。权值相同的边，先后顺序无所谓。

开始从头遍历排序后的边。

选边(1,2)，节点1 和节点2 不在同一个集合，所以生成树可以添加边(1,2)，并将节点1，节点2 放在同一个集合。
在这里插入图片描述选边(4,5)，节点4 和节点 5 不在同一个集合，生成树可以添加边(4,5) ，并将节点4，节点5 放到同一个集合。

在上面的讲解中，看图的话大家知道如何判断两个节点是否在同一个集合（是否有绿色的线连在一起），以及如何把两个节点加入集合（就在图中把两个节点连上）

但在代码中，如果将两个节点加入同一个集合，又如何判断两个节点是否在同一个集合呢？
- 用并查集

import java.util.*;class Edge {int l, r, val;Edge(int l, int r, int val) {this.l = l;this.r = r;this.val = val;}
}
public class Main {private static int n = 10001;private static int[] father = new int[n];// 并查集初始化public static void init() {for (int i = 0; i < n; i++) {father[i] = i;}}// 并查集的查找操作public static int find(int u) {if (u == father[u]) return u;return father[u] = find(father[u]);}public static void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int v = scanner.nextInt();int e = scanner.nextInt();List<Edge> edges = new ArrayList<>();int result_val = 0;for (int i = 0; i < e; i++) {int v1 = scanner.nextInt();int v2 = scanner.nextInt();int val = scanner.nextInt();edges.add(new Edge(v1, v2, val));}//对边进行排序edges.sort(Comparator.comparingInt(edge -> edge.val));// 并查集初始化init();// 从头开始遍历边for (Edge edge : edges) {int x = find(edge.l);int y = find(edge.r);if (x != y) {result_val += edge.val;join(x, y);}}System.out.println(result_val);scanner.close();}
}

Floyd 算法

【题目描述】

小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。

给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。

小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。请你帮助小明计算出每个观景计划的最短路径长度。

【输入描述】

第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。

接下来的 M 行，每行包含三个整数 u, v, w，表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。

接下里的一行包含一个整数 Q，表示观景计划的数量。

接下来的 Q 行，每行包含两个整数 start, end，表示一个观景计划的起点和终点。

【输出描述】

对于每个观景计划，输出一行表示从起点到终点的最短路径长度。如果两个景点之间不存在路径，则输出 -1。

【输入示例】

7 3 1 2 4 2 5 6 3 6 8 2 1 2 2 3

【输出示例】

4 -1

【提示信息】

从 1 到 2 的路径长度为 4，2 到 3 之间并没有道路。

1 <= N, M, Q <= 1000.

思路

Floyd算法核心思想是动态规划。

例如我们再求节点1 到节点9 的最短距离，用二维数组来表示即：grid[1][9]，如果最短距离是10 ，那就是 grid[1][9] =10。
那节点1 到节点9 的最短距离是不是可以由节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成呢？即 grid[1][9] = grid[1][5] + grid[5][9]
节点1 到节点5的最短距离是不是可以有节点1 到节点3的最短距离 + 节点3 到节点5 的最短距离组成呢？即 grid[1][5] = grid[1][3] + grid[3][5]
以此类推，节点1 到节点3的最短距离可以由更小的区间组成。那么这样我们是不是就找到了，子问题推导求出整体最优方案的递归关系呢。
节点1 到节点9 的最短距离可以由节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成，也可以有节点1 到节点7的最短距离 + 节点7 到节点9的最短距离的距离组成。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();  // 顶点数int m = sc.nextInt();  // 边数// 初始化距离矩阵，最大值设置为10005final int INF = 10005;int[][] grid = new int[n + 1][n + 1];// 初始化 grid 数组for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i != j) {grid[i][j] = INF;}}}// 输入边信息for (int i = 0; i < m; i++) {int p1 = sc.nextInt();int p2 = sc.nextInt();int val = sc.nextInt();grid[p1][p2] = val;grid[p2][p1] = val;  // 双向图}// Floyd-Warshall 算法//注意k要放在最外层for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (grid[i][k] + grid[k][j] < grid[i][j]) {grid[i][j] = grid[i][k] + grid[k][j];}}}}// 输出查询结果int z = sc.nextInt();  // 查询次数while (z-- > 0) {int start = sc.nextInt();int end = sc.nextInt();if (grid[start][end] == INF) {System.out.println(-1);} else {System.out.println(grid[start][end]);}}sc.close();  // 关闭Scanner}
}

dijkstra（朴素版）

【题目描述】

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。

小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。

小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

【输入描述】

第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。

接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。

【输出描述】

输出一个整数，代表小明从起点到终点所花费的最小时间。

思路

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组
minDist数组用来记录每一个节点距离源点的最小距离。
示例中节点编号是从1开始，所以为了让大家看的不晕，minDist数组下标我也从 1 开始计数，下标0 就不使用了，这样下标和节点标号就可以对应上了，避免大家搞混

模拟过程

0、初始化

minDist数组数值初始化为int最大值。

这里在强点一下 minDist数组的含义：记录所有节点到源点的最短路径，那么初始化的时候就应该初始为最大值，这样才能在后续出现最短路径的时候及时更新。
代码随想录朴素版dijkstra
源点（节点1）到自己的距离为0，所以 minDist[1] = 0

此时所有节点都没有被访问过，所以 visited数组都为0

模拟过程

以下为dijkstra 三部曲

1.1 第一次模拟

1、选源点到哪个节点近且该节点未被访问过

源点距离源点最近，距离为0，且未被访问。

2、该最近节点被标记访问过

标记源点访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：
在这里插入图片描述
更新 minDist数组，即：源点（节点1）到节点2 和节点3的距离。

源点到节点2的最短距离为1，小于原minDist[2]的数值max，更新minDist[2] = 1
源点到节点3的最短距离为4，小于原minDist[3]的数值max，更新minDist[3] = 4

1.2 第二次模拟

1、选源点到哪个节点近且该节点未被访问过

未访问过的节点中，源点到节点2距离最近，选节点2

2、该最近节点被标记访问过

节点2被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：
在这里插入图片描述
更新 minDist数组，即：源点（节点1）到节点6 、节点3 和节点4的距离。

以后的过程以此类推

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入节点数 n 和边数 mint n = sc.nextInt();int m = sc.nextInt();// 定义一个邻接矩阵，初始化为一个很大的数final int INF = Integer.MAX_VALUE;int[][] grid = new int[n + 1][n + 1];// 初始化 grid 为 INF，表示没有直接路径for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i != j) {grid[i][j] = INF;}}}// 输入边的信息for (int i = 0; i < m; i++) {int p1 = sc.nextInt();int p2 = sc.nextInt();int val = sc.nextInt();grid[p1][p2] = val;}// 设置起点和终点int start = 1;int end = n;// 存储从源点到每个节点的最短距离int[] minDist = new int[n + 1];// 记录顶点是否被访问过boolean[] visited = new boolean[n + 1];// 初始化最短距离数组，起始点到自身的距离为0，其他为INFfor (int i = 1; i <= n; i++) {minDist[i] = INF;}minDist[start] = 0;// 遍历所有节点，执行Dijkstra算法for (int i = 1; i <= n; i++) {int minVal = INF;int cur = -1;// 选择距离起点最近且未访问过的节点for (int v = 1; v <= n; v++) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}// 如果当前节点无法访问，则跳出循环（即剩下的节点不可达）if (cur == -1) break;visited[cur] = true; // 标记该节点已被访问// 更新非访问节点到源点的最短距离for (int v = 1; v <= n; v++) {if (!visited[v] && grid[cur][v] != INF && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];}}}// 输出结果，如果终点不可达，输出 -1if (minDist[end] == INF) {System.out.println(-1);} else {System.out.println(minDist[end]);}sc.close(); // 关闭Scanner}
}