图的存储
邻接矩阵
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); //n是节点数
int m = scanner.nextInt(); //m是边数
// 节点编号从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;
}
邻接表
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); //n是节点数
int m = scanner.nextInt(); //m是边数
// 节点编号从1到n，所以申请 n+1 这么大的数组
List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
graph.add(new LinkedList<>());
}
while (m-- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
// 使用邻接表表示 s -> t 是相连的
graph.get(s).add(t);
}
所有可达路径
题目描述 给定一个有 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
提示信息
用例解释：
有五个节点，其中的从 1 到达 5 的路径有两个，分别是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。
因为拥有多条路径，所以输出结果为：
1 3 5 1 2 4 5
或
1 2 4 5 1 3 5 都算正确。
数据范围：
图中不存在自环 图中不存在平行边 1 <= N <= 100 1 <= M <= 500
解题思路
使用dfs找到所有满足条件的路径
1.确认递归函数，参数
我们需要找到每条路径，那么需要一个变量cur来存放当前遍历到的节点
当前层节点==n，说明找到一条合适的路径，作为终止条件
需要全局变量来分别存储单一路径和路径集合
2.确认终止条件
如果当前cur==n,说明找到一条合适的路径，把当前路径加入路径集合，return
3.处理当前节点出发搜索的路径
走当前遍历节点x的下一个节点
- 首先是要找到 x节点指向了哪些节点
- 接下来就是将 选中的x所指向的节点，加入到 单一路径
- 进入下一层递归
- 最后就是回溯的过程，撤销本次添加节点的操作。
代码实现
邻接表
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int points = scanner.nextInt();
int edges = scanner.nextInt();
//节点数量，为了和编号对齐，所以申请n+1大小的空间
ArrayList<ArrayList<Integer>> map = new ArrayList<>(points+1);
for(int i = 0; i <= points; i++) {
map.add(new ArrayList<>());
}
while(edges-- > 0) { //添加边的连接关系，这里使用while
int s = scanner.nextInt();
int t = scanner.nextInt();
map.get(s).add(t);
}
//因为所有都是从1开始
path.add(1);
dfs(map, points, 1);
if(result.size() == 0) System.out.println(-1);
for(ArrayList<Integer> re:result) {
for(int i = 0;i < re.size()-1;i++) {
System.out.print(re.get(i)+" ");
}
System.out.println(re.get(re.size()-1));
}
}
static ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
static ArrayList<Integer> path = new ArrayList<Integer>();
public static void dfs(ArrayList<ArrayList<Integer>> map, int endPoint, int cur) {
if(cur == endPoint) {//终止条件
result.add(new ArrayList<>(path));
return;
}
for(int i:map.get(cur)) {//遍历当前节点连接的节点
path.add(i);
dfs(map, endPoint, i);
path.remove(path.size()-1);
}
}
邻接矩阵
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 到达节点n
if (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));
}
}
岛屿数量(深搜)
题目描述 给定一个由 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 提示信息
根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。
数据范围：
1 <= N, M <= 50
解题思路
遇到一个没有标记过的陆地节点，就对其进行标记，技术去+1。之后再把与其联接的陆地节点都标记。
遇到边界或者海洋直接跳过
代码实现
1.不写终止条件，只有符合要求才能继续DFS
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
int result = 0;
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
visited[i][j] = true;
result++;//遇到没访问过的陆地+1
dfs(map,visited, i, j);//把所有与其链接的陆地都标记为true
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
public static void dfs(int[][] map, boolean[][]visited, int x, int y) {
for(int i = 0 ; i < 4 ; i++) {
int nextx = x+dir[0][i];
int nexty = y+dir[1][i];
//不满足条件，跳过
if(nextx < 0 || nexty < 0 || nextx >= map.length || nexty >= map[0].length)continue;
//没有访问过，同时是陆地
if(!visited[nextx][nexty] && map[nextx][nexty] != 0) {
visited[nextx][nexty] = true;
dfs(map, visited, nextx, nexty);
}
}
}
2.写终止条件，所有节点都进行DFS,用终止条件判断，不合法时再return
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
int result = 0;
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
// visited[i][j] = true;
result++;//遇到没访问过的陆地+1
dfs(map,visited, i, j);//把所有与其链接的陆地都标记为true
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
public static void dfs(int[][] map, boolean[][]visited, int x, int y) {
if(visited[x][y] || map[x][y] == 0)return; //不满足条件
visited[x][y] = true; //标记为访问过
for(int i = 0 ; i < 4 ; i++) {
int nextx = x+dir[0][i];
int nexty = y+dir[1][i];
//不满足条件，跳过
if(nextx < 0 || nexty < 0 || nextx >= map.length || nexty >= map[0].length)continue;
dfs(map, visited, nextx, nexty);
}
}
}
理论上来讲，版本一的效率更高一些，因为避免了 没有意义的递归调用，在调用dfs之前，就做合法性判断。 但从写法来说，可能版本二 更利于理解一些。（不过其实都差不太多）
都是dfs，写法却不一样，有时候有终止条件，有时候连终止条件都没有，其实这就是根本原因，两种写法而已。
岛屿数量(广搜)
解题思路
和BFS理论基础一样，如果是陆地节点，且没有标记，进入BFS后，先标记，之后遍历队列元素，四周符合要求的节点加入队列同时标记
注意事项
这里有一个广搜中很重要的细节：
只要 加入队列就代表走过，就需要标记，而不是从队列拿出来的时候再去标记走过。
如果从队列拿出节点，再去标记这个节点走过，就会发生下图所示的结果，会导致很多节点重复加入队列。
超时写法 （从队列中取出节点再标记，注意代码注释的地方）
queue<pair<int, int>> que;
que.push({x, y});
while(!que.empty()) {
pair<int ,int> cur = que.front(); que.pop();
int curx = cur.first;
int cury = cur.second;
visited[curx][cury] = true; // 从队列中取出在标记走过
for (int i = 0; i < 4; i++) {
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过
if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
que.push({nextx, nexty});
}
}
加入队列 就代表走过，立刻标记，正确写法： （注意代码注释的地方）
Queue<int[]> queue = new LinkedList<int[]>();//建立队列
visited[x][y] = true;//// 只要加入队列立刻标记
queue.add(new int[] {x,y});
while(!queue.isEmpty()) {//开始遍历队列里的元素
int[] cur = queue.poll();//取出元素
for(int i = 0 ; i < 4; i++) {
int nextX = cur[0]+dir[0][i];
int nextY = cur[1]+dir[1][i];
if(nextX < 0 || nextX >= map.length || nextY < 0 || nextY >= map[0].length) {
continue;
}//越界跳过
//符合要求，加入队列
if(!visited[nextX][nextY] && map[nextX][nextY] == 1) {
queue.add(new int[] {nextX,nextY});
visited[nextX][nextY] = true;//立刻标记，避免重复访问
}
}
代码实现
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
int result = 0;
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
result++;//遇到没访问过的陆地+1
bfs(map,visited, i, j);//把所有与其链接的陆地都标记为true
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
public static void bfs(int[][] map, boolean[][]visited, int x, int y) {
Queue<int[]> queue = new LinkedList<int[]>();//建立队列
visited[x][y] = true;//置为true
queue.add(new int[] {x,y});
while(!queue.isEmpty()) {//开始遍历队列里的元素
int[] cur = queue.poll();//取出元素
for(int i = 0 ; i < 4; i++) {
int nextX = cur[0]+dir[0][i];
int nextY = cur[1]+dir[1][i];
if(nextX < 0 || nextX >= map.length || nextY < 0 || nextY >= map[0].length) {
continue;
}//越界跳过
//符合要求，加入队列
if(!visited[nextX][nextY] && map[nextX][nextY] == 1) {
queue.add(new int[] {nextX,nextY});
visited[nextX][nextY] = true;//立刻标记，避免重复访问
}
}
}
}
岛屿的最大面积
题目描述 给定一个由 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 输出示例 4 提示信息
样例输入中，岛屿的最大面积为 4。
数据范围：
1 <= M, N <= 50。
解题思路
搜索每个岛屿上'1’的数量，最后取最大值
写法一，dfs只处理下一个节点，即在主函数遇到岛屿就计数为1，dfs处理接下来的相邻陆地
写法二，dfs处理当前节点，即在主函数遇到岛屿就计数为0，dfs处理接下来的全部陆地
写法三，bfs,每次找到一个岛屿面积后和结果比大小，直到找完所有岛屿
注意事项 count应该作为全局变量，在每次DFS结束后和result比较取最大值，作为局部变量递归传进去比会出错
代码实现
(DFS，从下一个节点开始处理)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
int result = 0;
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
count = 1;
visited[i][j] = true;//当前节点记为true,从下一个节点开始处理
dfs(map,visited, i, j);//把所有与其链接的陆地都标记为true
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
static int count; //count要作为全局变量，这样每次递归结束才能得到正确的岛屿大小
public static void dfs(int[][] map, boolean[][]visited, int x, int y) {
for(int i = 0 ; i < 4 ; i++) {
int nextX = x+dir[0][i];
int nextY = y+dir[1][i];
if(nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length)continue;
if(!visited[nextX][nextY] && map[nextX][nextY] == 1) {
visited[nextX][nextY] = true;
count++;
dfs(map, visited, nextX, nextY);
}
}
}
(DFS，从当前节点开始处理)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
int result = 0;
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
count = 0; //从当前节点开始处理，符合要求直接进入DFS方法
dfs(map,visited, i, j);//把所有与其链接的陆地都标记为true
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
static int count; //count要作为全局变量，这样每次递归结束才能得到正确的岛屿大小
public static void dfs(int[][] map, boolean[][]visited, int x, int y) {
if(visited[x][y] || map[x][y] != 1)return;//终止条件
visited[x][y] = true; //当前节点置为true
count++;
for(int i = 0 ; i < 4 ; i++) {
int nextX = x+dir[0][i];
int nextY = y+dir[1][i];
if(nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length)continue;
dfs(map, visited, nextX, nextY);
}
}
(BFS)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
int result = 0;
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
count = 0;
bfs(map,visited, i, j);//把所有与其链接的陆地都标记为true
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
static int count; //count要作为全局变量，这样每次递归结束才能得到正确的岛屿大小
public static void bfs(int[][] map, boolean[][]visited, int x, int y) {
Queue<int[]> queue = new LinkedList<int[]>();
visited[x][y] = true; //当前位置的处理
count++;
queue.add(new int[] {x,y});
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for(int i = 0 ; i < 4 ; i++) {
int nextx = cur[0] + dir[0][i];
int nexty = cur[1] + dir[1][i];
if(nextx < 0 || nextx >= map.length || nexty < 0 || nexty >= map[0].length)continue;
if(!visited[nextx][nexty] && map[nextx][nexty] == 1) {
queue.add(new int[] {nextx, nexty});
visited[nextx][nexty] = true; //相连陆地的处理
count++;
}
}
}
}
孤岛的总面积
给定一个由 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 输出示例 1 提示信息
在矩阵中心部分的岛屿，因为没有任何一个单元格接触到矩阵边缘，所以该岛屿属于孤岛，总面积为 1。
数据范围：
1 <= M, N <= 50。
解题思路
DFS, 使用一个boolean 全局变量来确认单个岛屿是否为孤岛，使用一个count全局变量来确认当前岛屿的面积。如果为孤岛，在总面积上加入当前岛屿的面积
BFS, 使用一个局部变量area和boolean来确定当前岛屿的面积及是否为孤岛的情况，若是，则把area加入总面积中
从边缘开始遍历岛屿，把遍历到的岛屿都置为0，再统计没有置为0的岛屿
代码实现
BFS
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
int result = 0;
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
bfs(map,visited, i, j);//把所有与其链接的陆地都标记为true
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
static int count; //count要作为全局变量，这样每次递归结束才能得到正确的岛屿大小
public static void bfs(int[][] map, boolean[][]visited, int x, int y) {
Queue<int[]> queue = new LinkedList<int[]>();
boolean isolate = true;//当前岛屿是否为孤岛
int area = 0;//当前岛屿的面积
visited[x][y] = true; //当前位置的处理
area++;//当前陆地
queue.add(new int[] {x,y});
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for(int i = 0 ; i < 4 ; i++) {
int nextx = cur[0] + dir[0][i];
int nexty = cur[1] + dir[1][i];
if(nextx < 0 || nextx >= map.length || nexty < 0 || nexty >= map[0].length) {
isolate = false;//有超边界节点，说明不是孤岛
continue;
};
if(!visited[nextx][nexty] && map[nextx][nexty] == 1) {
queue.add(new int[] {nextx, nexty});
visited[nextx][nexty] = true; //相连陆地的处理
area++;//加上相邻的陆地
}
}
}
if(isolate)count += area;//找完整个岛，若不为孤岛，加入其面积
}
DFS
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
int result = 0;
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
//从当前节点开始，岛屿面积为0,默认为孤岛
count = 0;
notIsolate = false;
dfs(map,visited, i, j);//把所有与其链接的陆地都标记为true
//如果dfs结束发现是孤岛，把面积加入结果中
if(!notIsolate)result += count;
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
static int count; //count要作为全局变量，这样每次递归结束才能得到正确的岛屿大小
static boolean notIsolate; //记录当前岛是否为孤岛
public static void dfs(int[][] map, boolean[][]visited, int x, int y) {
if(visited[x][y] || map[x][y] != 1)return ;
visited[x][y] = true;
count++;
for(int i = 0 ; i < 4 ; i++) {
int nextx = x + dir[0][i];
int nexty = y + dir[1][i];
if(nextx < 0 || nextx >= map.length || nexty < 0 || nexty >= map[0].length) {
notIsolate = true; //不符合条件，说明不是孤岛
continue;
}
dfs(map, visited, nextx, nexty);
}
}
置为0的方法（dfs,bfs同理）
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
int result = 0;
//从边缘找岛屿，找到的岛屿标记为0
for(int i = 0; i < n ; i++) {//从矩阵的左侧和右侧查找
if(map[i][0] == 1)bfs(map, i, 0);
if(map[i][m-1] == 1)bfs(map,i,m-1);
}
for(int j = 0 ; j < m ; j++) {//从矩阵的上和下进行查找
if(map[0][j] == 1)bfs(map, 0, j);
if(map[n-1][j] == 1)bfs(map, n-1, j);
}
//查找剩下的孤岛
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1)result++;
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
public static void bfs(int[][] map, int x, int y) {
Queue<int[]> queue = new LinkedList<int[]>();
map[x][y] = 0; //标记为0
queue.add(new int[] {x,y});
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for(int i = 0 ; i < 4; i++) {
int nextx = cur[0] + dir[0][i];
int nexty = cur[1] + dir[1][i];
if(nextx < 0 || nextx >= map.length || nexty < 0 || nexty >= map[0].length) {
continue;
}
if( map[nextx][nexty] == 1) {
map[nextx][nexty] = 0; //相连是岛屿的位置标记为0
queue.add(new int[] {nextx, nexty});
}
}
}
}
沉没岛屿
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（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 <= M, N <= 50。
解题思路
和上题孤岛的总面积解题方法大同小异
1.多增加一个DFS或BFS方法用于沉没孤岛(将孤岛置为0).先使用BFS或DFS确认当前岛屿是否为孤岛，若为孤岛，使用新增的方法将其沉没
2.从边缘对矩阵进行遍历，找到不为孤岛的岛屿，标记为2；之后再遍历整个矩阵，把原来是2的位置标记为1，原来为1的位置标记为0.
代码实现
直接确定孤岛的方法(BFS，DFS均可)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
int result = 0;
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
notIsolate = false;
bfs(map,visited, i, j);//把所有与其链接的陆地都标记为true
if(!notIsolate)dfs1(map, i, j);
}
}
}
for(int[] arr: map) {
for(int i : arr) {
System.out.print(i+" ");
}
System.out.println();
}
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
static boolean notIsolate;
public static void bfs(int[][] map, boolean[][]visited, int x, int y) {
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {x,y});
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for(int i = 0 ; i < 4; i++) {
int nextx = cur[0] + dir[0][i];
int nexty = cur[1] + dir[1][i];
if(nextx < 0 || nextx >= map.length || nexty < 0 || nexty >= map[0].length) {
notIsolate = true;
continue;
}
if(!visited[nextx][nexty] && map[nextx][nexty] == 1) {
visited[nextx][nexty] = true;
queue.add(new int[] {nextx, nexty});
}
}
}
}
public static void dfs1(int[][]map, int x, int y) {
if(map[x][y] != 1)return;
map[x][y] = 0;
for(int i = 0 ; i < 4 ; i++) {
int nextx = x + dir[0][i];
int nexty = y + dir[1][i];
if(nextx < 0 || nextx >= map.length || nexty < 0 || nexty >= map[0].length) {
continue;
}
dfs1(map, nextx, nexty);
}
}
遍历非孤岛的方法(BFS，DFS均可)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
boolean[][] visited = new boolean[n][m];//记录是否访问
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
int result = 0;
//从边缘找岛屿，找到的岛屿标记为2
for(int i = 0; i < n ; i++) {//从矩阵的左侧和右侧查找
if(map[i][0] == 1)bfs(map, i, 0);
if(map[i][m-1] == 1)bfs(map,i,m-1);
}
for(int j = 0 ; j < m ; j++) {//从矩阵的上和下进行查找
if(map[0][j] == 1)bfs(map, 0, j);
if(map[n-1][j] == 1)bfs(map, n-1, j);
}
//把剩下的孤岛标记为0，原来标记为2的岛重新标记为1
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 1)map[i][j] = 0;
if(map[i][j] == 2)map[i][j] = 1;
}
}
for(int[] arr: map) {
for(int i : arr) {
System.out.print(i+" ");
}
System.out.println();
}
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
public static void bfs(int[][] map, int x, int y) {
Queue<int[]> queue = new LinkedList<int[]>();
map[x][y] = 2; //标记为2
queue.add(new int[] {x,y});
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for(int i = 0 ; i < 4; i++) {
int nextx = cur[0] + dir[0][i];
int nexty = cur[1] + dir[1][i];
if(nextx < 0 || nextx >= map.length || nexty < 0 || nexty >= map[0].length) {
continue;
}
if( map[nextx][nexty] == 1) {
map[nextx][nexty] = 2; //相连是岛屿的位置标记为2
queue.add(new int[] {nextx, nexty});
}
}
}
}
水流问题
题目描述 现有一个 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 <= 100。
解题思路
1.朴素想法：每个节点都DFS,看是否能到达两边界
2.优化思路：逆流，从第一组边界和第二组边界的每个位置逆流而上(DFS)，两个同时走到过的位置就是符合要求的位置
代码实现
朴素想法
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
//把剩下的孤岛标记为0，原来标记为2的岛重新标记为1
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
edge1 = false;
edge2 = false;
boolean[][] visited = new boolean[n][m];//记录是否访问,这里以每个位置开始都要重新记录，不然之前用过的会用不了
dfs(map, i, j, map[i][j],visited);
if(edge1 && edge2) {
System.out.println(i+" "+j);
}
}
}
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
static boolean edge1; //到第一组边界
static boolean edge2;//到第二组边界
public static void dfs(int[][] map, int x, int y, int last, boolean[][] visited) {
if(map[x][y] > last || visited[x][y]) {
return;
}
visited[x][y] = true;
for(int i = 0 ; i < 4 ; i++) {
int nextx = x+dir[0][i];
int nexty = y+dir[1][i];
if(nextx < 0 || nexty < 0 ) {
edge1 = true;
continue;
}
if(nextx >= map.length || nexty >= map[0].length) {
edge2 = true;
continue;
}
dfs(map, nextx, nexty, map[x][y],visited);
}
}
逆流向上，找从两组开始同时能访问到的点
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
boolean[][] edge1 = new boolean[n][m]; //存储第一组边界逆流的状态
boolean[][] edge2 = new boolean[n][m]; //第二组边界逆流的状态
for(int i = 0 ; i < n ; i++) { //左边和下边，从低向高遍历
dfs(map, i, 0, map[i][0], edge1);
dfs(map, i, m - 1, map[i][m - 1], edge2);
}
for(int j = 0 ; j < m ; j++) { //上边和右边，从低向高遍历
dfs(map, 0, j, map[0][j], edge1);
dfs(map, n - 1, j, map[n - 1][j], edge2);
}
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(edge1[i][j] && edge2[i][j]) {//节点从第一边界和第二边界出发都能遍历到，说明是合适的位置
System.out.println(i+" "+j);
}
}
}
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
public static void dfs(int[][] map, int x, int y, int last, boolean[][] visited) {
if(map[x][y] < last || visited[x][y]) {
return;
}
visited[x][y] = true;
for(int i = 0 ; i < 4 ; i++) {
int nextx = x+dir[0][i];
int nexty = y+dir[1][i];
if(nextx < 0 || nexty < 0 || nextx >= map.length || nexty >= map[0].length) {
continue;
}
dfs(map, nextx, nexty, map[x][y],visited);
}
}
建造最大岛屿
给定一个由 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 输出示例 6 提示信息
对于上面的案例，有两个位置可将 0 变成 1，使得岛屿的面积最大，即 6。
数据范围：
1 <= M, N <= 50。
解题思路
1.暴力解法 把每个水的位置都看做陆地，使用DFS/BFS，每次遍历一遍，找当前最大岛屿面积并比较，最后得到最大岛屿面积。
时间复杂度:遍历地图 n^2 , DFS n^2, 总时间复杂度 n^4
2.优化想法
- 1.遍历一遍地图，标记出各个不同的岛屿的岛屿面积，并使用map存储岛屿及其对应的面积。这个过程时间复杂度 n * n 。
- 分明是两个for循环下面套这一个dfs，时间复杂度怎么回事 n * n呢？
，n * n这个方格地图中，每个节点我们就遍历一次，并不会重复遍历。
- 2.遍历空位，寻找空位的上下左右是否存在岛屿，若存在，从map中加入该岛屿的面积。 每次使用set记录当前位置为陆地时相邻的岛屿标记，防止出错。这个过程时间复杂度 n * n 。
- 3.其他注意点： 为防止所有节点都为陆地的情况，需要设置boolean变量判断
整个解法的时间复杂度，为 n * n + n * n 也就是 n^2。
代码实现
暴力解法
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
int result = 0;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 0) {//DFS遍历每一个水的位置，找到最大岛屿面积
area = 0;//当前岛屿面积
boolean[][] visited = new boolean[n][m];//记录当前节点是否遍历
map[i][j] = 1;
dfs(map, i, j, visited);
result = Math.max(area, result);
map[i][j] = 0;
}else {
area = 0;//当前岛屿面积
boolean[][] visited = new boolean[n][m];//记录当前节点是否遍历
dfs(map, i, j, visited);
result = Math.max(area, result);
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
static int area = 0;
public static void dfs(int[][] map, int x, int y, boolean[][] visited) {
if(map[x][y] != 1 || visited[x][y]) {
return;
}
visited[x][y] = true;
area++;
for(int i = 0 ; i < 4 ; i++) {
int nextx = x+dir[0][i];
int nexty = y+dir[1][i];
if(nextx < 0 || nexty < 0 || nextx >= map.length || nexty >= map[0].length) {
continue;
}
dfs(map, nextx, nexty, visited);
}
}
优化解法
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];//记录矩阵
for(int i = 0 ; i < n; i++) {
for(int j = 0; j< m; j++) {
map[i][j] = scanner.nextInt();
}
}
//用来记录岛屿及其面积
HashMap<Integer, Integer> grid = new HashMap<Integer, Integer>();
//用来记录当前位置相连的岛屿
HashSet<Integer> set = new HashSet<Integer>();
//岛屿标记从2开始，和1，0做区分
mark = 2;
//记录是否整个地图全为陆地的情况，防止后面得到结果出错
boolean allgrid = true;
boolean[][] visited = new boolean[n][m];//记录整张地图岛屿的遍历情况
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 0)allgrid = false;
if(!visited[i][j] && map[i][j] == 1) {
area = 0;//当前岛屿面积
dfs(map, i, j, visited);
grid.put(mark, area);//记录当前标签岛屿面积
mark++;//统计完当前岛屿，更换新标签
}
}
}
int result = 0;
if(allgrid)result = n * m;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(map[i][j] == 0) {
int curSize = 1;//水变为陆地
set.clear(); //清除上次相邻岛屿的情况
for(int k = 0 ; k < 4 ; k++) {//遍历当前位置的相邻位置，找相邻岛屿
int nextx = i + dir[0][k];
int nexty = j + dir[1][k];
if(nextx < 0 || nexty < 0 || nextx >= map.length || nexty >= map[0].length) {
continue;
}
int curMark = map[nextx][nexty];//找到相邻岛屿的标记
//如果当前岛屿相邻情况已经统计过，或没有该岛屿标记，跳过
if(set.contains(curMark) || !grid.containsKey(curMark))continue;
//加入当前岛屿标记，作为已经统计过的标志
set.add(curMark);
//加入相邻岛屿的面积
curSize += grid.get(curMark);
}
//更新岛屿面积的最大值
result = Math.max(curSize, result);
}
}
}
System.out.println(result);
}
static int[][] dir = new int[][] {{0,0,-1,1},{-1,1,0,0}};//用来连接节点的不同位置四个方向
static int area = 0;//记录当前岛屿的面积
static int mark; //用于区分每个岛屿的标记
public static void dfs(int[][] map, int x, int y, boolean[][] visited) {
if(map[x][y] != 1 || visited[x][y]) {
return;
}
visited[x][y] = true;
map[x][y] = mark;
area++;
for(int i = 0 ; i < 4 ; i++) {
int nextx = x+dir[0][i];
int nexty = y+dir[1][i];
if(nextx < 0 || nexty < 0 || nextx >= map.length || nexty >= map[0].length) {
continue;
}
dfs(map, nextx, nexty, visited);
}
}
字符串接龙
字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列：
序列中第一个字符串是 beginStr。
序列中最后一个字符串是 endStr。
每次转换只能改变一个字符。
转换过程中的中间字符串必须是字典 strList 中的字符串，且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 输出示例 4 提示信息 从 startStr 到 endStr，在 strList 中最短的路径为 abc -> dbc -> dec -> def，所以输出结果为 4，如图：
数据范围：
2 <= N <= 500
解题思路
把每个字符串看做一个节点，整个图看做为无向图
节点之间如何连接：如果相差一个字符不同，那就说明有连接
怎样找到最短路径: 使用广搜更合适，因为广搜找到的第一个路径就是最短路径。深搜还需要考虑很多。
因为是无向图，所以需要使用HashMap记录当前节点是否走过，避免死循环
BFS中遍历每个字符串，使用a-z进行替换，如果替换后的新字符串等于endStr说明找到终点，如果新字符串在strList中，且没有访问过，说明这个点之间有连接，把该点加入队列。
代码实现
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//用于存储字符串列表
HashSet<String> strList = new HashSet<String>();
String beginStr = scanner.next();
String endStr = scanner.next();
for(int i = 0 ; i < n ; i++) {
String str = scanner.next();
strList.add(str);
}
// 记录strSet里的字符串是否被访问过，同时记录路径长度
HashMap<String, Integer> visited = new HashMap<String, Integer>();
visited.put(beginStr, 1);
System.out.println(bfs(visited, strList, beginStr, endStr));
}
public static int bfs(HashMap<String, Integer> visited, HashSet<String> strList, String beginStr, String endStr) {
Queue<String> queue = new LinkedList<String>();
queue.add(beginStr);
while(! queue.isEmpty()) {
//当前单词
String word = queue.poll();
//当前路径
int path = visited.get(word);
//遍历当前单词的每个位置
for(int i = 0 ; i < word.length(); i++) {
//将当前String转为StringBuilder，方便进行下一步操作
StringBuilder newWord = new StringBuilder(word);
//每个位置进行字母替换
for(char j = 'a'; j <= 'z'; j++) {
//StringBuilder进行替换
newWord.setCharAt(i, j);
//得到新字符串
String newStr = newWord.toString();
//如果新字符串就是最后一个字符串，说明找到答案
if(newStr.equals(endStr)) {
return path+1;
}
//如果新字符串在strList，并且visited中没有标记，说明当前字符串可以走到新字符串的位置
if(strList.contains(newStr) && !visited.containsKey(newStr)) {
visited.put(newStr, path+1);
queue.add(newStr);
}
}
}
}
//找不到路径，返回0
return 0;
}
有向图的完全可达性
给定一个有向图，包含 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 输出示例 1 提示信息
从 1 号节点可以到达任意节点，输出 1。
数据范围：
1 <= N <= 100； 1 <= K <= 2000。
解题思路
1.DFS,使用visited数组遍历相连节点，同时记录节点是否访问过，注意终止条件。注意DFS有两种写法，和之前一样，一种是从当前开始查找，另一种是从下一节点开始查找
2.BFS,遍历到连通节点记为访问过，看最后visited数组的访问情况
DFS（处理下一个要访问的节点）
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
boolean[] visited = new boolean[n+1];
visited[1] = true; //当前节点提前置为true
ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>(n+1);
for(int i = 0 ; i <= n ; i++) {
map.add(new ArrayList<Integer>());
}
while(k -- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
map.get(s).add(t);
}
dfs(map, visited, n, 1);
boolean flag = false;
for(int i = 1 ; i < n+1; i++) {
if(!visited[i]) {
flag = true;
System.out.println(-1);
}
}
if(!flag) {
System.out.println(1);
}
}
public static void dfs(ArrayList<ArrayList<Integer>> map, boolean[] visited, int cur) {
for(int i: map.get(cur)) {
if(!visited[i]) {
visited[i] = true;
dfs(map, visited, endPoint, i);
}
}
}
DFS(处理当前节点)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
boolean[] visited = new boolean[n+1];
// visited[1] = true;
ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>(n+1);
for(int i = 0 ; i <= n ; i++) {
map.add(new ArrayList<Integer>());
}
while(k -- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
map.get(s).add(t);
}
dfs(map, visited, 1);
boolean flag = false;
for(int i = 1 ; i < n+1; i++) {
if(!visited[i]) {
flag = true;
System.out.println(-1);
break;
}
}
if(!flag) {
System.out.println(1);
}
}
public static void dfs(ArrayList<ArrayList<Integer>> map, boolean[] visited, int cur) {
if(visited[cur])return;
visited[cur] = true; //当前节点的判断在DFS中处理
for(int i: map.get(cur)) {
dfs(map, visited, i);
}
}
BFS
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
boolean[] visited = new boolean[n+1];
ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>(n+1);
for(int i = 0 ; i <= n ; i++) {
map.add(new ArrayList<Integer>());
}
while(k -- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
map.get(s).add(t);
}
bfs(map, visited, 1);
boolean flag = false;
for(int i = 1 ; i < n+1; i++) {
if(!visited[i]) {
flag = true;
System.out.println(-1);
break;
}
}
if(!flag) {
System.out.println(1);
}
}
public static void bfs(ArrayList<ArrayList<Integer>> map, boolean[] visited, int cur) {
Queue<Integer> queue = new LinkedList<Integer>();
visited[cur] = true;
queue.add(cur);
while(!queue.isEmpty()) {
int key = queue.poll();
for(int i: map.get(key)) {
if(!visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
岛屿的周长
给定一个由 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 输出示例 14 提示信息
岛屿的周长为 14。
数据范围：
1 <= M, N <= 50。
解题思路
如何确定岛屿的周长
- 计算每个陆地的上下左右位置，如果该位置为0或者超出地图边界，则计入周长的计算
- 可以使用BFS,或者直接遍历每个陆地方块的上下左右
- 岛屿总面积 = 陆地个数 * 4 - 相邻陆地个数 * 2
有一对相邻两个陆地，边的总数就要减2，如图红线部分，有两个陆地相邻，总边数就要减2
直接遍历整个岛屿，遇到为1的陆地判断有无相邻岛屿，同时增加总l岛屿面积。
通过四周计算(BFS)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];
boolean[][] visited = new boolean[n][m];
for(int i = 0 ; i < n; i++) {
for(int j = 0; j < m; j++) {
map[i][j] = scanner.nextInt();
}
}
for(int i = 0 ; i < n; i++) {
for(int j = 0 ; j < m; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
bfs(map, visited, i, j);
break;
}
}
}
System.out.println(circle);
}
static int[][] dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
static int circle = 0;
public static void bfs(int[][] map, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {x, y});
visited[x][y] = true;
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for(int i = 0 ; i < 4 ; i++) {
int nextx = cur[0] + dir[i][0];
int nexty = cur[1] + dir[i][1];
if(nextx < 0 || nextx >= map.length || nexty < 0 || nexty >= map[0].length || map[nextx][nexty] == 0) {
circle++;
continue;
}
if(!visited[nextx][nexty]) {
visited[nextx][nexty] = true;
queue.add(new int[] {nextx, nexty});
}
}
}
}
通过面积和相邻岛屿个数计算
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] map = new int[n][m];
boolean[][] visited = new boolean[n][m];
for(int i = 0 ; i < n; i++) {
for(int j = 0; j < m; j++) {
map[i][j] = scanner.nextInt();
}
}
int land = 0;
int surround = 0;
//周长 = 陆地*4 - 相邻岛屿数量 * 2
for(int i = 0 ; i < n; i++) {
for(int j = 0 ; j < m; j++) {
if(map[i][j] == 1) {
land++;
//寻找相邻方块
//检查上面
if(i - 1 >= 0 && map[i-1][j] == 1) {
surround++;
}
//检查左边
if(j - 1 >= 0 && map[i][j-1] == 1) {
surround++;
}
// 检查左，上，防止越界
//不检查右边和下边：防止重复
}
}
}
System.out.println(land * 4 - surround*2);
}
寻找存在路径
给定一个包含 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 输出示例 1 提示信息
数据范围：
1 <= M, N <= 100。
解题思路
本题可以使用DFS,也可以使用并查集。DFS的思路和之前的题类似，本题用并查集解决
题目中各个点是双向图链接，那么判断 一个顶点到另一个顶点有没有有效路径其实就是看这两个顶点是否在同一个集合里。
如何算是同一个集合呢，有边连在一起，就算是一个集合。
此时我们就可以直接套用并查集模板。
使用 join(int u, int v)将每条边加入到并查集。
最后 isSame(int u, int v) 判断是否是同一个根 就可以了。
代码实现
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
father = new int[n + 1];
//并查集初始化
for(int i = 1; i < father.length; i++) {
father[i] = i;
}
for(int i = 0 ; i < m ; i++) {
join(scanner.nextInt(), scanner.nextInt());
}
int source = scanner.nextInt();
int destination = scanner.nextInt();
if(find(source) == find(destination)) {
System.out.println(1);
}else {
System.out.println(0);
}
}
static int[] father;
//并查集寻根方法
public static int find(int u) {
return (u == father[u]) ? u : (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 boolean isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
冗余连接
有一个图，它是一棵树，他是拥有 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
数据范围：
1 <= N <= 1000.
解题思路
并查集可以解决什么问题：两个节点是否在一个集合，也可以将两个节点添加到一个集合中。
和上一道题查找存在的路径相似，因为是无向图，可以使用并查集存储连接关系。
使用for循环，依次把输入元素按边的关系加入并查集
先使用isSame()函数比较输入的元素是否已经连接，如果已经连接，直接返回此时的输入
按输入顺序把边加入到并查集中
代码实现
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
father = new int[n + 1];
//并查集初始化
for(int i = 1; i < father.length; i++) {
father[i] = i;
}
for(int i = 0 ; i < n ; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
if(isSame(u, v)) {
System.out.println(u+" "+v);
return;
}
join(u,v);
}
}
static int[] father;
//并查集寻根方法
public static int find(int u) {
return (u == father[u]) ? u : (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 boolean isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
冗余连接Ⅱ
有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：
现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：
输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。
输入描述 第一行输入一个整数 N，表示有向图中节点和边的个数。
后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边
输出描述 输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。 输入示例 3 1 2 1 3 2 3 输出示例 2 3 提示信息
在删除 2 3 后有向图可以变为一棵合法的有向树，所以输出 2 3
数据范围：
1 <= N <= 1000.
解题思路
本题的本质：一个有向图是由一颗有向树+一条边组成的，找到那条边删掉，使其恢复为有向树
还有若有多条边可以删除，请输出标准输入中最后出现的一条边，这说明在两条边都可以删除的情况下，要删顺序靠后的边！
我们来想一下 有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）。
也就是说我们找到入度为2的节点，删除一条指向该节点的边就行了
有入度为2的节点，有两种删除情况:
1.直接删最后那条输入的边
- 1 - 3, 2 - 3是两条指向入度为2的三的节点的边。那么直接删除最后一条输入的边即可
2.只能删除特定的一条边
- 节点3 的入度为 2，但在删除边的时候，只能删 这条边（节点1 -> 节点3），如果删这条边（节点4 -> 节点3），那么删后本图也不是有向树了（因为找不到根节点）。
综上，如果发现入度为2的节点，我们需要判断 删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。
没有入度为2的节点，说明此时图里有环（有向环）：
删除掉构成环的边就可以了。
具体实现
记录每条边，并统计节点入度
ArrayList<int[]> edge = new ArrayList<int[]>(); //用来存储边关系
int[] inDegree = new int[n+1]; //记录节点的入度
for(int i = 0 ; i < n ; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();
edge.add(new int[] {s,t}); //记录边关系
inDegree[t]++;//记录t的入度个数
}
前两种入度为2的情况，一定是删除指向入度为2的节点的两条边其中的一条，如果删了一条，判断这个图是一个树，那么这条边就是答案。
同时注意要从后向前遍历，因为如果两条边删哪一条都可以成为树，就删最后那一条。
ArrayList<Integer> doubleEdge = new ArrayList<Integer>();
for(int i = ds.n - 1 ; i >= 0; i--) {
if(inDegree[edge.get(i)[1]] == 2) {
doubleEdge.add(i);
}
}
//情况一,二
if(!doubleEdge.isEmpty()) {
if(ds.isTreeAfterRemoveEdge(edge, doubleEdge.get(0))) {
System.out.println(edge.get(doubleEdge.get(0))[0]+" "+edge.get(doubleEdge.get(0))[1]);
}else {
System.out.println(edge.get(doubleEdge.get(1))[0]+" "+edge.get(doubleEdge.get(1))[1]);
}
return;
}
再来看情况三，明确没有入度为2的情况，那么一定有向环，找到构成环的边就是要删除的边。
//情况三
ds.getRemovedEdge(edge);
}
解决本题要实现两个最为关键的函数：
isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树
getRemoveEdge() 确定图中一定有了有向环，那么要找到需要删除的那条边
此时就用到并查集了。
- isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树： 将所有边的两端节点分别加入并查集，遇到要 要删除的边则跳过，如果遇到即将加入并查集的边的两端节点 本来就在并查集了，说明构成了环。
如果顺利将所有边的两端节点（除了要删除的边）加入了并查集，则说明 删除该条边 还是一个有向树
public boolean isTreeAfterRemoveEdge(ArrayList<int[]> edge, int deleteEdge) {
init();//注意每次都要初始化并查集
for(int i = 0 ; i < n; i++) {
if(i == deleteEdge)continue;
if(isSame(edge.get(i)[0], edge.get(i)[1])) { //说明此时构成了环，不删deleteEdge而是删后一条
return false;
}
join(edge.get(i)[0], edge.get(i)[1]);
}
return true;
}
- getRemoveEdge()确定图中一定有了有向环，那么要找到需要删除的那条边： 将所有边的两端节点分别加入并查集，如果遇到即将加入并查集的边的两端节点 本来就在并查集了，说明构成了环。
//找到需要删除的那条边
public void getRemovedEdge(ArrayList<int[]> edge) {
init();//注意每次都要初始化并查集
for(int i = 0 ; i < edge.size() ; i++) {//遍历所有边
if(isSame(edge.get(i)[0], edge.get(i)[1])) {//并查集里有，说明这条边就是要删除的边
System.out.println(edge.get(i)[0]+" "+edge.get(i)[1]);
return;
}else {
join(edge.get(i)[0], edge.get(i)[1]);
}
}
}
代码实现
public class KamaCode {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
DisjointSet ds = new DisjointSet(n);
ArrayList<int[]> edge = new ArrayList<int[]>(); //用来存储边关系
int[] inDegree = new int[n+1]; //记录节点的入度
for(int i = 0 ; i < n ; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();
edge.add(new int[] {s,t}); //记录边关系
inDegree[t]++;//记录t的入度个数
}
//找删除的边，两种情况
//1.入度为2的节点，包含两种情况
//1.直接删最后一个入度为2节点
//2.删除最后一个可能导致成环，所以删倒数第二个
//2.没有入度为2的节点，说明成环
//删除构成环的边
//判断够没够成环：是不是在并查集还未添加的时候，两节点的根已经相同。
ArrayList<Integer> doubleEdge = new ArrayList<Integer>();
for(int i = ds.n - 1 ; i >= 0; i--) {
if(inDegree[edge.get(i)[1]] == 2) {
doubleEdge.add(i);
}
}
//情况一
if(!doubleEdge.isEmpty()) {
if(ds.isTreeAfterRemoveEdge(edge, doubleEdge.get(0))) {
System.out.println(edge.get(doubleEdge.get(0))[0]+" "+edge.get(doubleEdge.get(0))[1]);
}else {
System.out.println(edge.get(doubleEdge.get(1))[0]+" "+edge.get(doubleEdge.get(1))[1]);
}
return;
}
//情况二
ds.getRemovedEdge(edge);
}
}
class DisjointSet{
int n;
int[] father;
public DisjointSet(int n) {
this.n = n;
this.father = new int[n+1];
}
public void init() {
for(int i = 1 ;i < father.length; i++) {
father[i] = i;
}
}
public void join(int u, int v) {
u = find(u);
v = find(v);
if(u == v)return;
father[v] = u;
}
public int find(int u) {
return (u == father[u])? u: (father[u] = find(father[u]));
}
public boolean isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
//找到需要删除的那条边
public void getRemovedEdge(ArrayList<int[]> edge) {
init();//注意每次都要初始化并查集
for(int i = 0 ; i < edge.size() ; i++) {//遍历所有边
if(isSame(edge.get(i)[0], edge.get(i)[1])) {//并查集里有，说明这条边就是要删除的边
System.out.println(edge.get(i)[0]+" "+edge.get(i)[1]);
return;
}else {
join(edge.get(i)[0], edge.get(i)[1]);
}
}
}
public boolean isTreeAfterRemoveEdge(ArrayList<int[]> edge, int deleteEdge) {
init();//注意每次都要初始化并查集
for(int i = 0 ; i < n; i++) {
if(i == deleteEdge)continue;
if(isSame(edge.get(i)[0], edge.get(i)[1])) { //说明此时构成了环，不删deleteEdge而是删后一条
return false;
}
join(edge.get(i)[0], edge.get(i)[1]);
}
return true;
}
}
说些什么吧！