代码随想录二刷|图论7
图论
一、基础知识
1 无向图
（1）度：一个顶点连n条边就度为n
（2）权
加权无向图：有边长的无向图
（3）通道：两个顶点之间有一些边和点，并且没有重复的边
路：两个顶点之间有一些边和点，并且没有重复的边和点
（4）连通性
1）连通图：任意两点之间都有路相连
2）连通分量：极大连通子图
（连通子图，并且没有包含这个连通子图的连通图）
2 有向图
（1）度
入度：n条边指向顶点则入度为n
出度：从顶点发出n条边则出度为n
（2）权
加权有向图：有边长的无向图
（3）连通性
1）强连通：任意2个点可以相互到达。也就是任意两个点之间都有相互指向的有向路（任何一个点，都有到剩下所有点的有向路）
2）强连通分量：极大强连通子图
（强连通子图，并且没有包含这个强连通子图的强连通图）
3 图的构造
邻接表、邻接矩阵 或者用类
（1）邻接表
1）邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表
// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<list<int>> graph(n + 1); // 邻接表，list为C++里的链表
graph[1].push_back(3) 表示5--->3
//遍历点x能到的所有点i
for(int i:graph[x])
- 节点1 指向 节点3 和 节点5
- 节点2 指向 节点4、节点3、节点5
- 节点3 指向 节点4
- 节点4指向节点1
2）邻接表的优点：
- 对于稀疏图的存储，只需要存储边，空间利用率高
- 遍历节点连接情况相对容易
3）邻接表的缺点：
- 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
- 实现相对复杂，不易理解
（2）邻接矩阵
1）邻接矩阵 使用 二维数组 来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组
grid[i][j] = 6，表示 节点 i 指向 节点j ，边的权值为6
如果想表示无向图，即：grid[i][j] = 6，grid[j][i] = 6，表示节点i 与 节点j相互连通，权值为6
2）邻接矩阵的优点：
- 表达方式简单，易于理解
- 检查任意两个顶点间是否存在边的操作非常快
- 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。
3）邻接矩阵的缺点：
- 遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费
（3）类
4 图的遍历方式
- 深度优先搜索（dfs）
- 广度优先搜索（bfs）
二、深度优先搜索
1、dfs要点
（1）搜索方向，是认准一个方向搜，直到碰壁之后再换方向
（2）换方向是撤销原路径，回退一步，改为节点链接的下一个路径（回溯的过程）
2、dfs的举例
假设默认路径
那么接下来考虑下一个方向，先回溯退回5,遍历5的下一步选择接下来就选择5—4
在节点4这里，先选择6,到达终点，再回溯退回4,遍历4的下一步选择，接下来就选择4–3
3、dfs代码(也就是回溯)
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); 递归
回溯，撤销处理结果
}
}
4、深度优先搜索的三步走
（1）确定递归返回值和参数
（2）确定终止条件，以及终止条件处做什么
（3）遍历当前节点可以选择的下一个点（遍历递归树的一个层）
5、模板题：所有可达路径
题目描述
给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。
输入描述
第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边
后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径
输出描述
输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出 -1。
注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 1 3 5,而不是 1 3 5 ， 5后面没有空格！
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<int> path;
vector<vector<int>> res;
void dfs(int point, int n, vector<vector<int>>& graph) {
if (point == n) {
res.push_back(path);
return;
}
for (int i = 1; i < graph[point].size(); i++) {
if (graph[point][i]) {
path.push_back(i);
dfs(i, n, graph);
path.pop_back();
}
}
}
int main() {
int n;
int m;
cin >> n >> m;
vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++) {
int start;
int end;
cin >> start >> end;
graph[start][end] = 1;
}
path.push_back(1);
dfs(1, n, graph);
if (res.size() == 0) {
cout << -1 ;
return 0;
}
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[i].size(); j++) {
cout << res[i][j];
if (j < res[i].size()-1)
cout << " ";
}
if (i < res.size()-1)
cout << "\n";
}
return 0;
}
三、广度优先搜索
1、特点
广搜（bfs）是一圈一圈的搜索过程，和深搜（dfs）是一条路跑到黑然后再回溯
2、只要BFS只要搜到终点一定是一条最短路径
3、代码框架
（1）如何保存遍历到的点：
仅仅需要一个容器，能保存我们要遍历过的元素就行，用队列，用栈，用数组，都是可以的
这里选择用队列
（2）要点
1）用队列进行遍历，每次把队首拿出来，弹出，将队首可以走到的后面的点放进队尾，一直到队空
2）在入队的时候标记visit，因为如果在弹出的时候再标记就会导致一个点重复的加入队列
（3）举例
用一个方格地图，假如每次搜索的方向为 上下左右（不包含斜上方），那么给出一个start起始位置，那么BFS就是从四个方向走出第一步
（例子、图和代码来自代码随想录）
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que; // 定义队列
que.push({x, y}); // 起始节点加入队列
visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
while(!que.empty()) { // 开始遍历队列里的元素
pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
int curx = cur.first;
int cury = cur.second; // 当前节点坐标
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]) { // 如果节点没被访问过
que.push({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
输出示例
3
思路：每次遇到一个没有访问过的陆地，就是找到一个新岛,然后把与这个陆地相连的陆地全都标记为isited
无论是dfs还是bfs，都是为了找到与这个陆地相连的陆地
1、深度优先搜索
（1）版本1
没有明确的终止条件，用for循环内的判断条件排除
include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& 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.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的
visited[nextx][nexty] = true;
dfs(grid, visited, nextx, nexty);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
vector<vector<bool>> visited(n, vector<bool>(m, false));
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
visited[i][j] = true;
result++; // 遇到没访问过的陆地，+1
dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
}
}
}
cout << result << endl;
}
（2）版本2
1）无返回值，参数包括图、visited、当前坐标，n和m
然后标记当前点visited[i][j] = 1
2）终止条件：
再判断一个点之前，先判断他是不是要考虑的
水域–不考虑
已经访问—不考虑
越界—不考虑
3）从当前点（i，j）出发，遍历上下左右，因为一开始判断有效性，所以所有点都递归
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
void dfs(vector<vector<int>> &visited, vector<vector<int>> &graph, int i, int j,
int n, int m) {
if (i < 0 || i >= n || j < 0 || j >= m)
return;
if (visited[i][j])
return;
if (graph[i][j] == 0)
return;
visited[i][j] = 1;
for (int k = 0; k < 4; k++) {
int x = directioni[k] + i;
int y = directionj[k] + j;
dfs(visited, graph, x, y, n, m);
}
}
int main() {
int n;
int m;
int sum = 0;
cin>>n>>m;
vector<vector<int>> graph(n, vector<int>(m, 0));
vector<vector<int>> visited(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && graph[i][j]) {
sum++;
dfs(visited, graph, i, j, n, m);
}
}
}
cout << sum;
return 0;
}
2、广度优先搜索
（1）把当前找到的第一次出现的陆地作为起点，bfs遍历与他相邻的陆地
每次把队首拿出来，弹出，队首可以走到的后面的点如果是没有访问过的陆地就放进队尾并且标记，一直到队空
（2）在入队的时候标记visit，因为如果在弹出的时候再标记就会导致一个点重复的加入队列
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n;
int m;
int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
void bfs(vector<vector<int>> graph, vector<vector<int>> &visited, int startx,
int starty) {
queue<pair<int, int>> q;
q.push(make_pair(startx, starty));
visited[startx][starty] = 1;
while (!q.empty()) {
pair<int, int> now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = now.first + directioni[i];
int y = now.second + directionj[i];
if (x < 0 || x >= n || y < 0 || y >= m)
continue;
if (!visited[x][y] && graph[x][y]) {
q.push(make_pair(x, y));
visited[x][y] = 1;
}
}
}
}
int main() {
int sum = 0;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
vector<vector<int>> visited(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && graph[i][j]) {
sum++;
bfs(graph, visited, i, j);
}
}
}
cout << sum;
return 0;
}
岛屿的最大面积
题干
题目描述
给定一个由 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
思路
每次遇到第一个没有访问过的陆地，就给结果+1,然后把与这个陆地相连的陆地全都标记为visited并且面积+1
遇到第一个没有访问过的陆地就是遇到新的岛屿
无论是dfs还是bfs，都是为了找到与这个陆地相连的陆地，并且记录这个岛屿的面积
dfs
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
void dfs(vector<vector<int>> &visited, vector<vector<int>> &graph, int i, int j,
int n, int m, int &area) {
if (i < 0 || i >= n || j < 0 || j >= m)
return;
if (visited[i][j])
return;
if (graph[i][j] == 0)
return;
visited[i][j] = 1;
area++;
for (int k = 0; k < 4; k++) {
int x = directioni[k] + i;
int y = directionj[k] + j;
dfs(visited, graph, x, y, n, m,area);
}
}
int main() {
int n;
int m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
vector<vector<int>> visited(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && graph[i][j]) {
int area = 0;
dfs(visited, graph, i, j, n, m, area);
res = max(res, area);
}
}
}
cout << res;
return 0;
}
bfs
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n;
int m;
int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
int bfs(vector<vector<int>> graph, vector<vector<int>> &visited, int startx,
int starty) {
queue<pair<int, int>> q;
q.push(make_pair(startx, starty));
int area = 1;
visited[startx][starty] = 1;
while (!q.empty()) {
pair<int, int> now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = now.first + directioni[i];
int y = now.second + directionj[i];
if (x < 0 || x >= n || y < 0 || y >= m)
continue;
if (!visited[x][y] && graph[x][y]) {
q.push(make_pair(x, y));
visited[x][y] = 1;
area++;
}
}
}
return area;
}
int main() {
int res = 0;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
vector<vector<int>> visited(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && graph[i][j]) {
int t = bfs(graph, visited, i, j);
res = max(res, t);
}
}
}
cout << res;
return 0;
}
孤岛的总面积
题干
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述
输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。
思路
1、思路1
（1）每次遇到一个没有访问过的陆地，然后把与这个陆地相连的陆地全都标记为visited
（2）在标记岛屿陆地的过程中，如果岛屿有的点x < 0 || x >= n || y < 0 || y >= m，那么就是挨着边界的，isolate标记为0，标注这不是一个孤岛
以bfs为例子
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n;
int m;
int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
int bfs(vector<vector<int>> graph, vector<vector<int>> &visited, int startx,
int starty) {
int isolate = 1;
queue<pair<int, int>> q;
q.push(make_pair(startx, starty));
if (startx == 0 || startx == n - 1 || starty == 0 || starty == m - 1)
isolate = 0;
int area = 1;
visited[startx][starty] = 1;
while (!q.empty()) {
pair<int, int> now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = now.first + directioni[i];
int y = now.second + directionj[i];
if (x < 0 || x >= n || y < 0 || y >= m)
continue;
if (!visited[x][y] && graph[x][y]) {
q.push(make_pair(x, y));
visited[x][y] = 1;
if (x == 0 || x == n - 1 || y == 0 || y == m - 1)
isolate = 0;
area++;
}
}
}
if (isolate)
return area;
else
return 0;
}
int main() {
int res = 0;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
vector<vector<int>> visited(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && graph[i][j]) {
int t = bfs(graph, visited, i, j);
res += t;
}
}
}
cout << res;
return 0;
}
2、思路2(更具有普适性，可以兼容沉默孤岛)
从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的陆地
（代码随想录）
以dfs为例子
#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
int count; // 统计符合题目要求的陆地空格数量
void dfs(vector<vector<int>>& grid, int x, int y) {
grid[x][y] = 0;
count++;
for (int i = 0; i < 4; i++) { // 向四个方向遍历
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
// 超过边界
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
// 不符合条件，不继续遍历
if (grid[nextx][nexty] == 0) continue;
dfs (grid, nextx, nexty);
}
return;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
// 从左侧边，和右侧边 向中间遍历
for (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);
}
// 从上边和下边 向中间遍历
for (int j = 0; j < m; j++) {
if (grid[0][j] == 1) dfs(grid, 0, j);
if (grid[n - 1][j] == 1) dfs(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) dfs(grid, i, j);
}
}
cout << count << endl;
}
沉没孤岛
题干
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。
之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出将孤岛“沉没”之后的岛屿矩阵。 注意：每个元素后面都有一个空格
思路
先从四个边界开始遍历，把所有挨着边界的陆地用dfs/bfs记成2
剩下的1都是孤岛
输出的时候遇到2就输出1,遇到1就输出0,遇到0就输出0
#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
int count; // 统计符合题目要求的陆地空格数量
void dfs(vector<vector<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 (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
// 不符合条件
if (grid[nextx][nexty] == 0 || grid[nextx][nexty] == 2) continue;
dfs (grid, nextx, nexty);
}
return;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
// 从左侧边，和右侧边 向中间遍历
for (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);
}
// 从上边和下边 向中间遍历
for (int j = 0; j < m; j++) {
if (grid[0][j] == 1) dfs(grid, 0, j);
if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(grid[i][j]==1)cout<<0<<" ";
else if(grid[i][j]==2)cout<<1<<" ";
else cout<<0<<" ";
}
cout<<"\n";
}
return 0;
}
水流问题
题干
题目描述
现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。
矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。
输入描述
第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。
后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。
输出描述
输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。
思路
暴力
遍历每一个点，判断是否出发的水可以达到第一组边界和第二组边界
优化
从第一组边界上的节点 逆流而上，将遍历过的节点都标记上
同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上
然后两方都标记过的节点就是既可以流第一组边界也可以流第二组边界
逆流而上的过程由dfs和bfs实现
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n;
int m;
vector<vector<int>> res;
int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
void dfs(vector<vector<int>> &visited, vector<vector<int>> &graph, int i,
int j) {
if (i < 0 || i >= n || j < 0 || j >= m)
return;
if (visited[i][j])
return;
visited[i][j] = 1;
for (int k = 0; k < 4; k++) {
int x = directioni[k] + i;
int y = directionj[k] + j;
if (x < 0 || x >= n || y < 0 || y >= m)
continue;
if (graph[i][j] <= graph[x][y])
dfs(visited, graph, x, y);
}
}
int main() {
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
vector<vector<int>> firstbound(n, vector<int>(m, 0));
vector<vector<int>> secondbound(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
for (int i = 0; i < n; i++) {
dfs(firstbound, graph, i, 0);
dfs(secondbound, graph, i, m - 1);
}
for (int i = 0; i < m; i++) {
dfs(firstbound, graph, 0, i);
dfs(secondbound, graph, n - 1, i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (firstbound[i][j] && secondbound[i][j])
cout << i << " " << j << "\n";
}
}
return 0;
}
建造最大岛屿
题干
题目描述：
给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。
岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。
输入描述：
第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
思路
用一次深搜把每个岛屿的面积记录下来。
1、一次遍历地图，得出各个岛屿的面积，并对岛屿做编号记录。可以使用map记录，key为岛屿编号（岛屿的每个陆地都赋值为key），value为岛屿面积
2、再遍历地图，遍历0的方格（因为要将0变成1），并统计该格子以及周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积
（要注意，对于每个格子，都要做一个set记录已经考虑过的岛屿编号）
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n;
int m;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
unordered_map<int, int> mapping;
void dfs(vector<vector<int>> &visited, vector<vector<int>>& graph, int x, int y,
int key) {
if (x < 0 || x >= n || y < 0 || y >= m)
return;
if (visited[x][y])
return;
if (graph[x][y] == 0)
return;
visited[x][y] = 1;
graph[x][y] = key;
mapping[key]++;
for (int i = 0; i < 4; i++) {
int newx = x + dx[i];
int newy = y + dy[i];
if (newx < 0 || newx >= n || newy < 0 || newy >= m)
continue;
dfs(visited, graph, newx, newy, key);
}
}
int main() {
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
vector<vector<int>> visited(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
int all_land=1;
int key = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(graph[i][j]==0){
all_land=0;
}
if (!visited[i][j] && graph[i][j] == 1) {
dfs(visited, graph, i, j, key);
key++;
}
}
}
if(all_land){
cout<<n*m;
return 0;
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (graph[i][j] == 0) {
int temp = 1;
unordered_set<int> used_island;
for (int k = 0; k < 4; k++) {
int newx = i + dx[k];
int newy = j + dy[k];
if (newx < 0 || newx >= n || newy < 0 || newy >= m)
continue;
if (graph[newx][newy]) {
if (used_island.find(graph[newx][newy]) == used_island.end()) {
temp += mapping[graph[newx][newy]];
used_island.insert(graph[newx][newy]);
}
}
}
res = max(res, temp);
}
}
}
cout << res;
return 0;
}
字符串接龙
题干
题目描述
字典 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
思路
1、建模
字符串看作点，两个字符串之间可以转换则有边
（代码随想录）
2、广度优先搜索
因为求最短路径，广度优先搜索只要能找到路径就一定是最短
3、要记录访问过的字符串：因为是无向图
用map记录访问的字符串，同时记录到当前字符串走过的步数
visit[s]表示走到s字符串的最短步数
4、用set村strlist，便于确定字符串是否属于strlist
#include <bits/stdc++.h>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
int n;
string start;
string end;
unordered_set<string> strlist;
unordered_map<string, int> visit;
cin >> n;
cin >> start >> end;
for (int i = 0; i < n; i++) {
string t;
cin >> t;
strlist.insert(t);
}
queue<string> q;
q.push(start);
visit[start] = 1;
while (!q.empty()) {
string t = q.front();
q.pop();
for (int i = 0; i < t.size(); i++) {
string next = t;
for (int j = 0; j < 26; j++) {
if (next[i] == 'a' + j)
continue;
next[i] = 'a' + j;
if (next == end) {
visit[next] = visit[t] + 1;
cout << visit[next];
return 0;
}
if (strlist.find(next) == strlist.end())
continue;
if (visit[next])
continue;
q.push(next);
visit[next] = visit[t] + 1;
}
}
}
cout << 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
思路
遍历所有能到达的点，visit记录走过的点，最后遍历visit
dfs
#include <bits/stdc++.h>
#include <list>
#include <vector>
using namespace std;
void dfs(int n,vector<list<int>> graph,vector<int>& visit,int x){
if(visit[x])return;
visit[x]=1;
for(int i:graph[x]){
dfs(n,graph,visit,i);
}
}
int main() {
int n;
int k;
cin >> n >> k;
vector<list<int>> graph(n + 1);
vector<int> visit(n + 1, 0);
for (int i = 0; i < k; i++) {
int a;
int b;
cin >> a >> b;
graph[a].push_back(b);
}
dfs(n,graph,visit,1);
for (int i = 1; i <= n; i++) {
if (visit[i] == 0) {
cout << -1;
return 0;
}
}
cout << 1;
return 0;
}
bfs
#include <bits/stdc++.h>
#include <list>
#include <vector>
using namespace std;
int main() {
int n;
int k;
cin >> n >> k;
vector<list<int>> graph(n + 1);
vector<int> visit(n + 1, 0);
for (int i = 0; i < k; i++) {
int a;
int b;
cin >> a >> b;
graph[a].push_back(b);
}
queue<int> q;
q.push(1);
visit[1] = 1;
while (!q.empty()) {
int t = q.front();
int next;
q.pop();
for (int next:graph[t]) {
if (visit[next])
continue;
visit[next] = 1;
q.push(next);
}
}
for (int i = 1; i <= n; i++) {
if (visit[i] == 0) {
cout << -1;
return 0;
}
}
cout << 1;
return 0;
}
岛屿的周长
题干
题目描述
给定一个由 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
思路
遍历（以dfs为例）
（1）参数：ans值的是遍历到当前点(x,y)为止的周长
（2）终止条件：(x,y)越界，(x,y)已经访问过
（3）遍历(x,y)接下来可以去的点
1）如果(x,y)是陆地：
判断(nextx,nexty)是不是界外或水，如果是，ans++
2）(x,y)无论是陆地还是海洋，都进行下一个递归
#include <bits/stdc++.h>
#include <list>
#include <vector>
using namespace std;
int n;
int m;
int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
void dfs(vector<vector<int>> graph, vector<vector<int>> &visit, int x, int y,
int &ans) {
if (x < 0 || x >= n || y < 0 || y >= m)
return;
if (visit[x][y])
return;
visit[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nextx = x + directioni[i];
int nexty = y + directionj[i];
if (graph[x][y] == 1) {
if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m ||
graph[nextx][nexty] == 0) {
ans++;
}
}
dfs(graph, visit, nextx, nexty, ans);
}
}
int main() {
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
vector<vector<int>> visit(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
int ans = 0;
dfs(graph, visit, 0, 0, ans);
cout << ans;
return 0;
}
四、并查集
基础理论
1、并查集的作用：解决连通性问题
1）无向图当中，两个点是否有路相连（是否可达）
2）两个元素是否在一个集合里的问题
2、并查集的功能
- 将两个元素添加到一个集合
- 判断两个元素在不在同一个集合
3、表示
（1）father[A]=B 表示A联通B
（2）father[A]=B father[B]=C 表示A、B和C联通
（3）father[c]=c 表示c是根
如果两点根相同，那么他们就是联通的
判断联通性的原理：u和v在同一个子树上，就是联通
4、功能的实现
（1）寻根
递归：如果father[i]==i那么i就是根，否则继续递归find(father[i])
（2）将u和v联通（加入同一个集合）
1）先找根 find(u) find(v)
2）根相同就是连通的
3）根不同：则将根1和根2连在一起 father[root1]=father[root2]
（3）判断连个元素是否联通（在统一集合）
1）先找根 find(u) find(v)
2）根相同就是连通的
（4）初始化并查集
father[i]=i 自己是自己的根
5、路径压缩
如果深度过大，可以在寻找的过程中把每个节点的上一个点标记i成根（father[u]=find(u))
相当于从
到
（图片来自代码随想录）
int find(int u) {
if (u == father[u]) return u;
else return father[u] = find(father[u]); // 路径压缩
}
并查集模板
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
// 并查集初始化
void init() {
for (int i = 0; i < n; ++i) {
father[i] = i;
}
}
// 并查集里寻根的过程
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
u = find(u); // 寻找u的根
v = find(v); // 寻找v的根
if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
father[v] = u;
}
寻找存在的路径
题干
题目描述
给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。
你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。
输入描述
第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。
后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。
最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。
输出描述
输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。
思路
判断无向图中A到B的路径是否存在，并查集
#include <bits/stdc++.h>
using namespace std;
int find(int i,vector<int>&father){
if(father[i]==i)return i;
return find(father[i],father);
}
void join(int i,int j,vector<int>&father){
int i_root=find(i,father);
int j_root=find(j,father);
if(i_root==j_root)return;
father[i_root]=j_root;
}
int main(){
int n,m;
cin>>n>>m;
vector<int>father(n+1);
for(int i=1;i<=n;i++){
father[i]=i;
}
for(int i=0;i<m;i++){
int s;
int t;
cin>>s>>t;
join(s,t,father);
}
int start;
int end;
cin>>start>>end;
cout<<(find(start,father)==find(end,father));
return 0;
}
冗余连接
题干
题目描述
有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：
现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：
先请你找出冗余边，删除后，使该图可以重新变成一棵树。
输入描述
第一行包含一个整数 N，表示图的节点个数和边的个数。
后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。
输出描述
输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。
输入示例
3
1 2
2 3
1 3
输出示例
1 3
思路
对于每一条边，如果它链接的两个点的根不一样，也就是这两点在不同的树上，那么就不会成环；如果这两点有共同的根，也就是在同一个树上，就会成环
#include<bits/stdc++.h>
using namespace std;
int root(int x,vector<int>&father){
if(father[x]==x)return x;
else return root(father[x],father);
}
int main(){
int n;
int s,t;
cin>>n;
vector<int>father(n+1);
for(int i=1;i<=n;i++){
father[i]=i;
}
for(int i=0;i<n;i++){
cin>>s>>t;
int rs=root(s,father);
int rt=root(t,father);
if(rs==rt){
cout<<s<<" "<<t;
return 0;
}
father[rs]=rt;
}
return 0;
冗余连接II
题干
题目描述
有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：
现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：
输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。
输入描述
第一行输入一个整数 N，表示有向图中节点和边的个数。
后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边
输出描述
输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。
输入示例
3
1 2
1 3
2 3
输出示例
2 3
思路
1、两种大类情况
（1）有某个点入度为2：要删掉的边一定是指向入度为2的点的边
考虑那2个指向入度为2的点的边，判断删掉之后是否是有向树
（从后向前遍历找指向入度为2的点的边）
（2）有环：类似无向环删掉一条边
遍历所有边，将每条边加入并查集，如果有某一条边的两个点已经有同一个根了，那么就是环，删掉这条边
2、判断删掉一条边之后是不是有向树
（先初始化并查集）
（1）遍历所有边，将每条边加入并查集
边是u---->v的话，就是father[v]=u u是v的父亲
（2）遇到要删掉的边，跳过
（3）如果有某一条边的两个点有相同的根了，那么就是有向环，这样删掉之后不是有向树
bool is_tree(int s, int t) {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
for (int i = 0; i < n; i++) {
if (edges[i][0] == s && edges[i][1] == t)
continue;
if (same_tree(edges[i][0], edges[i][1]))
return 0;
link(edges[i][0], edges[i][1]);
}
return 1;
}
3、有向环条件下，选择删掉的一条边
（先初始化并查集）
（1）从前向后遍历所有边，将每条边加入并查集
边是u---->v的话，就是father[v]=u u是v的父亲
（2）如果有某一条边的两个点有相同的根了，那么就是有向环，删掉
int choose_delete() {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
for (int i =0; i <n; i++) {
if (same_tree(edges[i][0], edges[i][1]))
return i;
link(edges[i][0], edges[i][1]);
}
}
代码
#include <bits/stdc++.h>
using namespace std;
int n;
int edges[1001][2];
int father[1001];
int indegree[1001];
int root(int x) {
if (father[x] == x)
return x;
else
return root(father[x]);
}
bool same_tree(int x, int y) { return root(x) == root(y); }
void link(int x, int y) {
int rx = root(x);
int ry = root(y);
if (rx == ry)
return;
father[ry] = rx;
}
bool is_tree(int s, int t) {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
for (int i = 0; i < n; i++) {
if (edges[i][0] == s && edges[i][1] == t)
continue;
if (same_tree(edges[i][0], edges[i][1]))
return 0;
link(edges[i][0], edges[i][1]);
}
return 1;
}
int choose_delete() {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
for (int i =0; i <n; i++) {
if (same_tree(edges[i][0], edges[i][1]))
return i;
link(edges[i][0], edges[i][1]);
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> edges[i][0] >> edges[i][1];
indegree[edges[i][1]]++;
}
for (int i = n - 1; i >= 0; i--) {
if (indegree[edges[i][1]] == 2) {
if (is_tree(edges[i][0], edges[i][1])) {
cout << edges[i][0] << " " << edges[i][1];
return 0;
}
}
}
int delete_index = choose_delete();
cout << edges[delete_index][0] << " " << edges[delete_index][1];
return 0;
}
五、最小生成树
1、最小生成树的概念
（1）生成子图：包含图中所有顶点的子图
（2）生成树：是一个连通图的子图，它包含图中的所有顶点，并且是一个树
（3）最小生成树（MST，Minimum Spanning Tree）是一个连通加权图的子图，包含原图的所有顶点，边权和是最小的**（边权和最小的生成树）**
2、最小生成树任务
从n条边选取n-1条使得图中所有节点连接到一起，并且边的权值和最小
3、解法
（1）prim
prim算法是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中
1）prim核心三步
- 第一步，选距离生成树最近节点
- 第二步，最近节点加入生成树
- 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
一共选n-1条边，遍历n-1次，每次遍历都执行核心三步
2）minDist数组用来记录每一个节点距离最小生成树的最近距离
<1>minDist数组里的数值初始化为权值最大数+1
<2>除了最先加入最小生成树的节点以外，在一个点加入最小生成树之后它的minDist对应值就是在最小生成树里面的权值
<3>最小的权值和就是除了第一个加入的元素之外剩下的元素的MinDist之和
3）遍历
一共选n-1条边，遍历n-1次
4）如何更新非生成树节点到生成树的距离
遍历所有点，如果最小生成树外点j和新加入最小生成树的点相连，那么取这条边和minDist[j]当中较小值作为minDist[j]，最小生成树内点不改变minDist
#include <bits/stdc++.h>
using namespace std;
int main(){
int v;
int e;
cin>>v>>e;
vector<vector<int>>grid(v+1,vector<int>(v+1,0));
vector<int>minDist(v+1,10001);
vector<int>is_in(v+1,0);
int sum=0;
for(int i=0;i<e;i++){
int s;
int t;
int val;
cin>>s>>t>>val;
grid[s][t]=val;
grid[t][s]=val;
}
for(int j=1;j<v;j++){
int min_val=10002;
int min_id=-1;
for(int i=1;i<=v;i++){
if(min_val>minDist[i]&&!is_in[i]){
min_val=minDist[i];
min_id=i;
}
}
is_in[min_id]=1;
for(int i=1;i<=v;i++){
if(!is_in[i]&&grid[i][min_id]){
minDist[i]=min(minDist[i],grid[i][min_id]);
}
}
}
for(int i=2;i<=v;i++){
sum+=minDist[i];
}
cout<<sum;
return 0;
}
（2）Kruskal
1）Kruskal 是维护边的集合
2）Kruskal核心2步
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合（在同一个子树里，并查集），说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合（并查集连接）
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int l, r, val;
};
static bool cmp(Edge & a,Edge &b){
return a.val<b.val;
}
int father[10001];
int root(int x) {
if (father[x] == x)
return x;
else
return root(father[x]);
}
bool same_tree(int x, int y) { return root(x) == root(y); }
void link(int x, int y) {
int rx = root(x);
int ry = root(y);
if (rx == ry)
return;
father[ry] = rx;
}
int main(){
int v;
int e;
int sum=0;
cin>>v>>e;
vector<Edge>edges(e);
for(int i=1;i<=v;i++){
father[i]=i;
}
for(int i=0;i<e;i++){
cin>>edges[i].l>>edges[i].r>>edges[i].val;
}
sort(edges.begin(),edges.end(),cmp);
for(int i=0;i<e;i++){
if(!same_tree(edges[i].l,edges[i].r)){
sum+=edges[i].val;
link(edges[i].l,edges[i].r);
}
}
cout<<sum;
return 0;
}