More content：LeetCode hot100@图论
大纲
- 深搜与广搜
- 并查集
- 最小生成树
- Kruskal
- prim
- 拓扑排序
- 最短路算法
- dijkstra(单源)
- Bellman_ford(单源&负权)
- Floyd(多源)
代码框架
dfs
vector<vector<int>> result; // 保存符合条件的所有路径
vector<int> path; // 起点到终点的路径
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}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]; // 注意x并不是横坐标，而是行号
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; // 只要加入队列立刻标记，避免重复访问
}
}
}
}并查集
vector<int> fa(n+1, 0); // n根据题目中节点数量而定
// 并查集初始化
void init() {
for(int i = 1; i <= n; i++) fa[i] = i;
}
// 并查集里寻根的过程
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]); //路径压缩
}
// 判断 u 和 v是否属于同一个根
bool isSame(int u, int v) {
int fu = find(u);
int fv = find(v);
return fu == fv;
}
// 将v->u 这条边加入并查集
void merge(int u, int v) {
int fu = find(u);
int fv = find(v);
if(fu == fv) return ;
fa[fv] = fu;
}深搜与广搜
98. 所有可达路径✅
简单的dfs回溯，图可以用邻接矩阵或邻接表两种方式实现
注意两种方式的初始化不同
邻接矩阵：
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> graph;
vector<vector<int>> res;
vector<int> path;
void dfs(int cur) {
if(cur == n) {
res.push_back(path);
}
for(int i = 0; i < n; i++) {
if(!graph[cur-1][i]) continue;
path.push_back(i+1);
dfs(i+1);
path.pop_back(); //回溯
}
return ;
}
int main() {
cin >> n >> m;
graph.resize(n, vector<int>(n, 0)); //外层和内层vector都要初始化
int x, y;
for(int i = 0; i < m; i++) {
cin >> x >> y;
graph[x-1][y-1] = 1;
}
// for(int i = 0; i < n; i++) {
// for(int j = 0; j < n; j++) {
// cout << graph[i][j] << " ";
// }
// cout << endl;
// }
path.push_back(1);
dfs(1);
if(!res.size()) {
cout << -1;
return 0;
}
for(int i = 0; i < res.size(); i++) {
for(int j = 0; j < res[i].size() - 1; j++) {
cout << res[i][j] << " ";
}
cout << res[i][res[i].size() - 1] << endl;
}
return 0;
}邻接表：
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<list<int>> graph;
vector<vector<int>> res;
vector<int> path;
void dfs(int cur) {
if(cur == n) {
res.push_back(path);
return ;
}
for(int i : graph[cur-1]) {
path.push_back(i);
dfs(i);
path.pop_back(); //回溯
}
return ;
}
int main() {
cin >> n >> m;
graph.resize(n); //只需初始化外层vector，内层list本来就是动态的
int x, y;
for(int i = 0; i < m; i++) {
cin >> x >> y;
graph[x-1].push_back(y);
}
// for(int i = 0; i < n; i++) {
// for(int j = 0; j < graph[i].size(); j++) {
// cout << graph[i][j] << " ";
// }
// cout << endl;
// }
path.push_back(1);
dfs(1);
if(!res.size()) {
cout << -1;
return 0;
}
for(int i = 0; i < res.size(); i++) {
for(int j = 0; j < res[i].size() - 1; j++) {
cout << res[i][j] << " ";
}
cout << res[i][res[i].size() - 1] << endl;
}
return 0;
}99. 岛屿数量❌
核心思想是标记（类似并查集），有dfs和bfs两种方法
bfs要注意只要加入队列，立即标记该节点走过，否则会重复加入，可能超时
dfs：
#include<bits/stdc++.h>
using namespace std;
int n, m, res;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
vector<vector<int>> grid;
vector<vector<bool>> visited;
void dfs(int x, int y) { //x是行号，y是列号
//没写终止条件是因为下面循环里把非法情况都排除了
for(int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if(!visited[nextx][nexty] && grid[nextx][nexty]) {
visited[nextx][nexty] = true;
dfs(nextx, nexty);
}
}
}
int main() {
cin >> n >> m;
grid.resize(n, vector<int>(m));
visited.resize(n, vector<bool>(m, false));
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++) {
for(int j = 0; j < m; j++) {
if(!visited[i][j] && grid[i][j]) {
res++;
visited[i][j] = true;
dfs(i, j); //把与之相连的陆地都标记上作为一个整体
}
}
}
cout << res;
return 0;
}bfs：
#include<bits/stdc++.h>
using namespace std;
int n, m, res;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
vector<vector<int>> grid;
vector<vector<bool>> visited;
void bfs(int x, int y) {
queue<pair<int, int>> q;
q.push({x, y});
visited[x][y] = true;
while(!q.empty()) {
pair<int, int> cur = q.front();
q.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 >= n || nexty < 0 || nexty >= m) continue;
if(!visited[nextx][nexty] && grid[nextx][nexty]) {
q.push({nextx, nexty});
visited[nextx][nexty] = true;
}
}
}
}
int main() {
cin >> n >> m;
grid.resize(n, vector<int>(m));
visited.resize(n, vector<bool>(m, false));
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++) {
for(int j = 0; j < m; j++) {
if(!visited[i][j] && grid[i][j]) {
res++;
visited[i][j] = true;
bfs(i, j); //把与之相连的陆地都标记上作为一个整体
}
}
}
cout << res;
return 0;
}100. 岛屿的最大面积✅
跟99. 岛屿数量差别不大 搜索时加上面积计数器即可
#include<bits/stdc++.h>
using namespace std;
int n, m, res, area;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int row, int col) {
for(int i = 0; i < 4; i++) {
int nextx = row + dir[i][0];
int nexty = col + dir[i][1];
if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if(grid[nextx][nexty] && !visited[nextx][nexty]) {
visited[nextx][nexty] = true;
area++;
dfs(grid, visited, nextx, nexty);
}
}
}
int main() {
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
vector<vector<bool>> visited(n, vector<bool>(m, false));
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++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] && !visited[i][j]) {
area = 1;
visited[i][j] = true;
//dfs只处理下一个节点，即在主函数遇到岛屿就计数为1，dfs处理接下来的相邻陆地
dfs(grid, visited, i, j);
res = max(res, area);
}
}
}
cout << res << endl;
return 0;
}
101. 孤岛的总面积❌
要找到不靠边的陆地面积，只需要从周边陆地开始将周边靠陆地且相邻的陆地都变成海洋，然后再重新遍历地图统计此时还剩下的陆地即可
即使在将地图改造完统计孤岛时，在area++后也把陆地变成了海洋，因此无需visited数组标记，根本不会重复访问（已经变成了海洋）
#include<bits/stdc++.h>
using namespace std;
int n, m, res, area;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
void dfs(vector<vector<int>> &grid, int row, int col) {
for(int i = 0; i < 4; i++) {
int nextx = row + dir[i][0];
int nexty = col + dir[i][1];
if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if(grid[nextx][nexty]) {
area++;
grid[nextx][nexty] = 0;
dfs(grid, nextx, nexty);
}
}
}
int main() {
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
vector<vector<bool>> visited(n, vector<bool>(m, false));
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]) {
grid[i][0] = 0;
dfs(grid, i, 0);
}
if(grid[i][m-1]) {
grid[i][m-1] = 0;
dfs(grid, i, m-1);
}
}
//从第一行和最后一行向中间遍历
for(int i = 0; i < m; i++) {
if(grid[0][i]) {
grid[0][i] = 0;
dfs(grid, 0, i);
}
if(grid[n-1][i]) {
grid[n-1][i] = 0;
dfs(grid, n-1, i);
}
}
// for(int i = 0; i < n; i++) {
// for(int j = 0; j < m; j++) {
// cout << grid[i][j];
// }
// cout << endl;
// }
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j]) {
area = 1;
grid[i][j] = 0;
dfs(grid, i, j);
// cout << "i = " << i << ", j = " << j << ", area = " << area << endl;
res += area;
}
}
}
cout << res << endl;
return 0;
}102. 沉没孤岛✅
思路很简单：事先备份grid，先使用上题101. 孤岛的总面积的方法把孤岛找出来，再根据原数组中孤岛的位置对备份进行修改
还有一种思路：先把非孤岛标记从1改为2，此时孤岛为1，再把孤岛从1改为0（即沉没），最后把非孤岛标记从2再改回1
#include<bits/stdc++.h>
using namespace std;
int n, m, res, area;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
void dfs(vector<vector<int>> &grid, int row, int col) {
for(int i = 0; i < 4; i++) {
int nextx = row + dir[i][0];
int nexty = col + dir[i][1];
if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if(grid[nextx][nexty]) {
area++;
grid[nextx][nexty] = 0;
dfs(grid, nextx, nexty);
}
}
}
int main() {
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
vector<vector<int>> res(n, vector<int>(m, 0));
vector<vector<bool>> visited(n, vector<bool>(m, false));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> grid[i][j];
res[i][j] = grid[i][j];
}
}
//从第一列和最后一列向中间遍历
for(int i = 0; i < n; i++) {
if(grid[i][0]) {
grid[i][0] = 0;
dfs(grid, i, 0);
}
if(grid[i][m-1]) {
grid[i][m-1] = 0;
dfs(grid, i, m-1);
}
}
//从第一行和最后一行向中间遍历
for(int i = 0; i < m; i++) {
if(grid[0][i]) {
grid[0][i] = 0;
dfs(grid, 0, i);
}
if(grid[n-1][i]) {
grid[n-1][i] = 0;
dfs(grid, n-1, i);
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j]) res[i][j] = 0;
if(j == m) cout << res[i][j];
else cout << res[i][j] << " ";
}
cout << endl;
}
return 0;
}103. 水流问题❌
可以直观想到：遍历每个点，看该点能否既到达左上边界，也能到达右下边界，但超时了（因为遍历是n*m，深搜时也是n*m）
以空间换时间：定义两个数组，先从左上边界开始逆流标记，再从右下边界逆流标记，被两个标记都标记过的点就是要找的点
#include<bits/stdc++.h>
using namespace std;
int n, m;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int row, int col) {
for(int i = 0; i < 4; i++) {
int nextx = row + dir[i][0];
int nexty = col + dir[i][1];
if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if(!visited[nextx][nexty] && grid[row][col] <= grid[nextx][nexty]) {
visited[nextx][nexty] = true;
dfs(grid, visited, nextx, nexty);
}
}
}
int main() {
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
vector<vector<bool>> lu(n, vector<bool>(m, false));
vector<vector<bool>> rd(n, vector<bool>(m, false));
for(int i = 0; i < n; i++) {
lu[i][0] = true;
dfs(grid, lu, i, 0); //遍历左边界
rd[i][m-1] = true;
dfs(grid, rd, i, m-1); //遍历右边界
}
for(int i = 0; i < m; i++) {
lu[0][i] = true;
dfs(grid, lu, 0, i); //遍历上边界
rd[n-1][i] = true;
dfs(grid, rd, n-1, i); //遍历下边界
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(lu[i][j] && rd[i][j]) cout << i << " " << j << endl;
}
}
return 0;
}104. 建造最大岛屿❌
从暴力入手（遍历地图，尝试将每一个0改成1，然后去搜索地图中的最大的岛屿面积），但是要优化
事先把每个岛屿的面积记录下来（用map，key是岛屿编号，把该岛屿的每块都标记为标号，从2开始，value是面积），当把某块0变为1后，统计其周边连接的岛屿之和
#include<bits/stdc++.h>
using namespace std;
int n, m;
int id, cnt, area;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
unordered_map<int, int> mp; //key:岛屿编号 value:岛屿面积
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int row, int col) {
for(int i = 0; i < 4; i++) {
int nextx = row + dir[i][0];
int nexty = col + dir[i][1];
if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if(grid[nextx][nexty] && !visited[nextx][nexty]) {
visited[nextx][nexty] = true;
grid[nextx][nexty] = id;
cnt++;
dfs(grid, visited, nextx, nexty);
}
}
}
int main() {
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
vector<vector<bool>> visited(n, vector<bool>(m, false));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
bool is_allland = true;
id = 2;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!grid[i][j]) is_allland = false;
if(grid[i][j] && !visited[i][j]) {
visited[i][j] = true;
cnt = 1;
grid[i][j] = id;
dfs(grid, visited, i, j);
mp.insert(make_pair(id++, cnt));
}
}
}
if(is_allland) {
cout << n * m << endl;
return 0;
}
// for(int i = 0; i < n; i++) {
// for(int j = 0; j < m; j++) {
// cout << grid[i][j] << " ";
// }
// cout << endl;
// }
// for(unordered_map<int, int>::iterator it = mp.begin(); it != mp.end(); it++)
// cout << it->first << " " << it->second << endl;
int res = 0;
unordered_set<int> visited_island; //记录累加过的岛屿
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!grid[i][j]) {
visited_island.clear();
area = 1;
for(int k = 0; k < 4; k++) {
int nextx = i + dir[k][0];
int nexty = j + dir[k][1];
if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if(visited_island.count(grid[nextx][nexty])) continue; //说明已经加过一次了
area += mp[grid[nextx][nexty]];
visited_island.insert(grid[nextx][nexty]);
}
res = max(res, area);
}
}
}
cout << res << endl;
return 0;
}110. 字符串接龙❌
没领会到这题是让求最短路径的长度，且不用找出具体路径
最短路径适合BFS，因为广搜只要搜到了终点，那么一定是最短的路径
可以先构建好邻接表，方便BFS
#include<bits/stdc++.h>
using namespace std;
string beginStr, endStr;
unordered_map<string, vector<string>> graph; //邻接表
unordered_map<string, int> visited; //记录字符串，防止重复搜, 同时记录路径长度
void buildGraph(vector<string> &strs);
int dif_letters(const string &a, const string &b);
void bfs();
void buildGraph(vector<string> &strs) {
for(int i = 0; i < strs.size(); i++) {
vector<string> v;
for(int j = 0; j < strs.size(); j++) {
if(i == j) continue;
if(dif_letters(strs[i], strs[j]) == 1) {
v.push_back(strs[j]);
}
}
graph.insert(make_pair(strs[i], v));
}
return ;
}
int dif_letters(const string &a, const string &b) {
int diff = 0;
for (int i = 0; i < a.size(); i++) {
if (a[i] != b[i]) diff++;
}
return diff;
}
void bfs() {
queue<string> q;
q.push(beginStr);
visited.insert(make_pair(beginStr, 1));
while(!q.empty()) {
string node = q.front();
int path = visited[node];
// cout << "node:" << node << endl << "insert:";
q.pop();
for(const auto &s : graph[node]) {
if(s == endStr) {
cout << path+1 << endl;
return ;
}
if(visited.count(s)) continue;
visited.insert(make_pair(s, path+1));
// cout << s << " ";
q.push(s);
}
}
}
int main() {
int n;
cin >> n;
cin >> beginStr >> endStr;
vector<string> strs(n);
for(int i = 0; i < n; i++) {
cin >> strs[i];
}
strs.push_back(beginStr);
strs.push_back(endStr);
//graph(n+2, vector<string>(n+2));
buildGraph(strs);
// for(auto &i : strs) cout << i << endl;
// for(auto it = graph.begin(); it != graph.end(); ++it) {
// const auto& front = it->first;
// const auto& ss = it->second;
// cout << front << ": ";
// for(const auto &s : ss) {
// cout << s << " ";
// }
// cout << endl;
// }
bfs();
return 0;
}105. 有向图的完全可达性✅
构建邻接表+dfs
visited数组在此题既标记是否走过（防止死循环+优化），又是是否连通的依据
注意此题不用回溯，因为不用调头（只是测试连通性，直接标记就好，如果是找一条可行路径就需要回溯了）
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> graph; //邻接表
vector<bool> visited;
void buildGraph(vector<pair<int, int>> &edges) {
for(int i = 0; i < m; i++) {
graph[edges[i].first].push_back(edges[i].second);
}
return ;
}
void dfs(int node) {
for(int i = 0; i < graph[node].size(); i++) {
if(visited[graph[node][i]]) continue;
visited[graph[node][i]] = true;
dfs(graph[node][i]);
}
return ;
}
int main() {
cin >> n >> m;
vector<pair<int, int>> edges;
int x, y;
for(int i = 0; i < m; i++) {
cin >> x >> y;
edges.push_back(make_pair(x, y));
}
graph.resize(n+1);
buildGraph(edges);
visited.resize(n+1, false);
visited[1] = true;
dfs(1);
for(int i = 2; i <= n; i++) {
if(visited[i] == false) {
cout << "-1" << endl;
return 0;
}
}
cout << "1" << endl;
return 0;
}106. 岛屿的周长✅
不用深搜广搜 直接遍历每一块陆地 检查周围四块 如果是水周长就+1
#include<bits/stdc++.h>
using namespace std;
int n, m, res;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int main() {
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
int x, y;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
int nearx, neary;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j]) { //遍历陆地周围的水的数量就是周长
for(int k = 0; k < 4; k++) {
nearx = i + dir[k][0];
neary = j + dir[k][1];
if(nearx < 0 || nearx >= n || neary < 0 || neary >= m) {
res++;
continue;
}
if(grid[nearx][neary] == 0) {
res++;
}
}
}
}
}
cout << res << endl;
return 0;
}并查集
107. 寻找存在的路径✅
并查集模板题
#include<bits/stdc++.h>
using namespace std;
int n, m, bg, ed;
vector<int> fa;
void init() {
for(int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int u, int v) {
int fu = find(u);
int fv = find(v);
if(fu == fv) return ;
fa[fv] = fu;
}
bool isSame(int u, int v) {
int fu = find(u);
int fv = find(v);
return fu == fv;
}
int main() {
cin >> n >> m;
fa.resize(n+1);
int x, y;
vector<pair<int, int>> edges;
for(int i = 0; i < m; i++) {
cin >> x >> y;
edges.push_back(make_pair(x, y));
}
cin >>bg >> ed;
init();
for(int i = 0; i < m; i++) {
merge(edges[i].first, edges[i].second);
}
if(isSame(bg, ed)) cout << 1 << endl;
else cout << 0 << endl;
return 0;
}108. 冗余连接✅
我的思路：遍历每条边，看去掉它用并查集检查是否依然连通（繁琐，相当于用了n-1套并查集）
标准思路：只需遍历每一条边，判断节点A和节点B是否在同一个集合，如果不在，就merge；如果在，说明再将这条边加上就一定会出现环（只用了一套并查集）
//我的思路
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> fa;
void init() {
for(int i = 0; i < n; i++) fa[i] = i;
}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int u, int v) {
int fu = find(u);
int fv = find(v);
if(fu == fv) return ;
fa[fv] = fu;
}
bool isSame(int u, int v) {
int fu = find(u);
int fv = find(v);
return fu == fv;
}
int main() {
cin >> n;
fa.resize(n+1);
int x, y;
vector<pair<int, int>> edges;
for(int i = 0; i < n; i++) {
cin >> x >> y;
edges.push_back(make_pair(x, y));
}
//遍历每条边，看去掉它是否依然连通
for(int i = n-1; i >= 0; i--) { //为了输出要求，从后往前遍历
init();
// cout << "去掉边" << edges[i].first << edges[i].second << endl;
for(int j = 0; j < n; j++) {
if(i == j) continue;
merge(edges[j].first, edges[j].second);
}
// for(int k = 1; k <= n; k++) cout << "fa[" << k << "] = " << fa[k] << endl;
bool flag = true;
for(int k = 1; k < n; k++) { //检测是否连通
if(!isSame(0, k)) {
// cout << "false" << endl;
flag = false;
break;
}
}
if(flag) {
cout << edges[i].first << " " << edges[i].second << endl;
return 0;
}
}
}//标准思路
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> fa;
void init() {
for(int i = 0; i < n; i++) fa[i] = i;
}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int u, int v) {
int fu = find(u);
int fv = find(v);
if(fu == fv) return ;
fa[fv] = fu;
}
bool isSame(int u, int v) {
int fu = find(u);
int fv = find(v);
return fu == fv;
}
int main() {
cin >> n;
fa.resize(n+1);
init();
int x, y;
for(int i = 0; i < n; i++) {
cin >> x >> y;
if(isSame(x, y)) {
cout << x << " " << y << endl;
return 0;
}
merge(x, y);
}
}109. 冗余连接II❌
与上题类似，但要更复杂一些，详见代码随想录题解
#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> edges;
vector<int> inDegree; //统计入度
vector<int> twoDegree; //记录入度为2的边（如果有的话就两条边）
vector<int> fa;
void init() {
for(int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int u, int v) {
int fu = find(u);
int fv = find(v);
if(fu == fv) return ;
fa[fv] = fu;
}
bool isSame(int u, int v) {
int fu = find(u);
int fv = find(v);
return fu == fv;
}
//删一条边之后判断是不是树
bool isTree(int deleteEdge) {
init(); // 初始化并查集
for(int i = 0; i < n; i++) {
if(i == deleteEdge) continue; //相当于删除了该边
if(isSame(edges[i][0], edges[i][1])) { //构成有向环了，一定不是树
return false;
}
merge(edges[i][0], edges[i][1]);
}
return true;
}
//在有向图里找到删除的那条边，使其变成树
void findRemoveEdge() {
init(); // 初始化并查集
for(int i = 0; i < n; i++) { //遍历所有的边
if(isSame(edges[i][0], edges[i][1])) { //构成有向环了，就是要删除的边
cout << edges[i][0] << " " << edges[i][1];
return;
} else{
merge(edges[i][0], edges[i][1]);
}
}
}
int main() {
cin >> n;
fa.resize(n+1);
inDegree.resize(n+1, 0);
init();
int x, y;
for(int i = 0; i < n; i++) {
cin >> x >> y;
inDegree[y]++;
edges.push_back({x, y});
}
//遍历找出入度为2的边
for(int i = n-1; i >= 0; i--) { //倒序遍历是为了题目要求，输出最后出现的一条边
if(inDegree[edges[i][1]] == 2) {
twoDegree.push_back(i);
}
}
if(twoDegree.size() > 0) {
if(isTree(twoDegree[0])) {
cout << edges[twoDegree[0]][0] << " " << edges[twoDegree[0]][1];
} else{
cout << edges[twoDegree[1]][0] << " " << edges[twoDegree[1]][1];
}
return 0;
}
//明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
findRemoveEdge();
}最小生成树
53. 寻宝（第七期模拟笔试）✅
最小生成树模板题
Kruskal算法是维护边的集合，而prim算法是维护节点的集合
Kruskal时间复杂度为nlogn，n为边的数量；prim时间复杂度为O(n^2)，n为点的数量
因此， 稀疏图用Kruskal算法更优，稠密图用prim算法更优（如果题目要求输出选中的边，用Kruskal会方便很多）
Kruskal：
#include<bits/stdc++.h>
using namespace std;
int n, m;
int fa[10005];
struct edge {
int u, v, c;
};
bool cmp(edge x, edge y) {
return x.c < y.c;
}
void init() {
for(int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int u, int v) {
int fu = find(u);
int fv = find(v);
if(fu == fv) return ;
fa[fv] = fu;
}
bool isSame(int u, int v) {
int fu = find(u);
int fv = find(v);
return fu == fv;
}
int main() {
cin >> n >> m;
vector<edge> edges;
struct edge ed;
for(int i = 0; i < m; i++) {
cin >> ed.u >> ed.v >> ed.c;
edges.push_back(ed);
}
sort(edges.begin(), edges.end(), cmp);
// for(const auto &ed : edges) cout << ed.u << " " << ed.v << " " << ed.c << endl;
init();
int cnt = 0;
int res = 0;
for(const auto &ed : edges) {
if(isSame(ed.u, ed.v)) continue;
merge(ed.u, ed.v);
res += ed.c;
cnt++;
if(cnt == n-1) break;
}
cout << res << endl;
return 0;
}prim：
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
int x, y, k;
cin >> n >> m;
vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10001)); //默认最大值
while(m--) {
cin >> x >> y >> k;
//因为是双向图，所以两个方向都要填上
grid[x][y] = k;
grid[y][x] = k;
}
vector<int> minDist(n + 1, 10001); //所有节点到最小生成树的最小距离
vector<bool> isInTree(n + 1, false); //这个节点是否在树里
//循环n-1次，建立n-1条边
for (int i = 1; i < n; i++) {
//第一步：选距离生成树最近的节点
int cur = -1; //选中哪个节点，加入最小生成树
int minVal = INT_MAX;
for(int j = 1; j <= n; j++) { //这里下标从1开始
if(!isInTree[j] && minDist[j] < minVal) {
minVal = minDist[j];
cur = j;
}
}
//第二步：最近节点（cur）加入生成树
isInTree[cur] = true;
//第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
for(int j = 1; j <= n; j++) {
if(!isInTree[j] && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
}
}
}
int res = 0;
for(int i = 2; i <= n; i++) { //不计第一个顶点，因为统计的是边的权值，n个节点有n-1条边
res += minDist[i];
}
cout << res << endl;
return 0;
}
拓扑排序
117. 软件构建❌
拓扑排序模板题
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> inDegree(n, 0);
unordered_map<int, vector<int>> umap;// 记录文件依赖关系
vector<int> res;
int u, v;
for(int i = 0; i < m; i++) {
cin >> u >> v;
inDegree[v]++;
umap[u].push_back(v);
}
queue<int> que;
for(int i = 0; i < n; i++) {
if(inDegree[i] == 0) {
que.push(i);
}
}
while(!que.empty()) {
int cur = que.front();
que.pop();
res.push_back(cur);
vector<int> files = umap[cur]; //获取该文件指向的文件
//如果该文件有后续文件，要把它们的入度减一，相当于在图中删除cur节点
if(!files.empty()) {
for(const auto &file : files) {
inDegree[file]--;
if(!inDegree[file]) que.push(file);
}
}
}
if(res.size() == n) {
cout << res[0];
for(int i = 1; i < n; i++) cout << " "<< res[i];
} else {
cout << -1 << endl;
}
return 0;
}最短路算法
47. 参加科学大会（第六期模拟笔试）
最短路径dijkstra算法模板题
朴素版：采用邻接矩阵存储图，适用于稠密图
堆优化版：采用邻接表存储图，适用于稀疏图
//dijkstra算法朴素版
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m, s, e, w;
cin >> n >> m;
vector<vector<int>> grid(n+1, vector<int>(n+1, INT_MAX));
for(int i = 0; i < m; i++) {
cin >> s >> e >> w;
grid[s][e] = w;
}
vector<int> minDist(n+1, INT_MAX);
vector<bool> visited(n+1, false);
minDist[1] = 0;
for(int i = 1; i <= n; i++) {
int cur = 1;
int minVal = INT_MAX;
for(int v = 1; v <= n; v++) {
if(!visited[v] && minDist[v] < minVal) {
cur = v;
minVal = minDist[v];
}
}
visited[cur] = true;
for(int v = 1; v <= n; v++) {
if(!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
minDist[v] = minDist[cur] + grid[cur][v];
}
}
// 打印日志：
// cout << "select:" << cur << endl;
// for (int v = 1; v <= n; v++) cout << v << ":" << minDist[v] << " ";
// cout << endl << endl;
}
if(minDist[n] == INT_MAX) cout << -1 << endl;
else cout << minDist[n] << endl;
return 0;
}//dijkstra算法堆优化版
#include<bits/stdc++.h>
using namespace std;
//小顶堆
class myComparison {
public:
//谓词
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
//定义一个结构体来表示带权重的边
struct Edge {
int to; //邻接顶点
int val; //边的权重
Edge(int t, int w): to(t), val(w) {} //构造函数
};
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<list<Edge>> grid(n + 1);
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid[p1].push_back(Edge(p2, val));
}
vector<int> minDist(n + 1, INT_MAX);
vector<bool> visited(n + 1, false);
//优先队列中存放pair<节点，源点到该节点的权值>
priority_queue<pair<int, int>, vector<pair<int, int>>, myComparison> pq;
pq.push(pair<int, int>(1, 0));
minDist[1] = 0;
while(!pq.empty()) {
pair<int, int> cur = pq.top();
pq.pop();
if(visited[cur.first]) continue;
visited[cur.first] = true;
for(Edge edge : grid[cur.first]) {
if(!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) {
minDist[edge.to] = minDist[cur.first] + edge.val;
pq.push(pair<int, int>(edge.to, minDist[edge.to]));
}
}
}
if(minDist[n] == INT_MAX) cout << -1 << endl;
else cout << minDist[n] << endl;
return 0;
}
94. 城市间货物运输 I
最短路径Bellman_ford算法模板题（适用于边权值含负数的情况）
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> edges;
int x, y, v;
for(int i = 0; i < m; i++) {
cin >> x >> y >> v;
edges.push_back({x, y, v});
}
int begin = 1;
int end = n;
vector<int> minDist(n+1, INT_MAX);
minDist[begin] = 0;
//松弛n-1次
for(int k = 1; k <= n-1; k++) {
for(const vector<int> &edge : edges) { //遍历每一条边
int from = edge[0];
int to = edge[1];
int value = edge[2];
//核心
if(minDist[from] != INT_MAX && minDist[to] > minDist[from] + value) {
minDist[to] = minDist[from] + value;
}
}
}
if(minDist[end] == INT_MAX) cout << "unconnected" << endl;
else cout << minDist[end] << endl;
return 0;
}95. 城市间货物运输 II
依然是最短路径Bellman_ford算法模板题，在上题的基础上增加了含有负权回路的情况
核心思路就是在上题的基础上，再多松弛一次，看minDist数组是否发生变化
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> edges;
int x, y, v;
for(int i = 0; i < m; i++) {
cin >> x >> y >> v;
edges.push_back({x, y, v});
}
int begin = 1;
int end = n;
vector<int> minDist(n+1, INT_MAX);
minDist[begin] = 0;
bool circle = false;
//松弛n-1次
for(int k = 1; k <= n; k++) {
for(const vector<int> &edge : edges) { //遍历每一条边
int from = edge[0];
int to = edge[1];
int value = edge[2];
//核心
if(k == n) {
if(minDist[from] != INT_MAX && minDist[to] > minDist[from] + value) circle = true;
} else {
if(minDist[from] != INT_MAX && minDist[to] > minDist[from] + value) {
minDist[to] = minDist[from] + value;
}
}
}
}
if(circle) cout << "circle" << endl;
else if(minDist[end] == INT_MAX) cout << "unconnected" << endl;
else cout << minDist[end] << endl;
return 0;
}96. 城市间货物运输 III
依然是最短路径Bellman_ford算法模板题，在95. 城市间货物运输 II的基础上增加了最短路径途径节点数量的限制
既然之前是松弛n-1次，那么现在改为松弛k+1次即可（因为途径节点不包括1和n，因此实际上是k+2个节点，即n~n-1对应k+2~k+1）
但要注意，在本题计算minDist数组的时候，基于了本次松弛的minDist数值，而不是上一次松弛时的minDist的数值，所以在每次计算minDist时，要基于对所有边上一次松弛的minDist数值才行，所以我们要记录上一次松弛的minDist（之所以与之前不同，是因为本题既可能包含负权回路，又对约束次数做了限制）
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m, src, dst, cnt;
cin >> n >> m;
vector<vector<int>> edges;
int x, y, v;
for(int i = 0; i < m; i++) {
cin >> x >> y >> v;
edges.push_back({x, y, v});
}
cin >> src >> dst >> cnt;
vector<int> minDist(n+1, INT_MAX);
vector<int> minDist_copy(n+1); //用来记录上一次遍历的结果
minDist[src] = 0;
//松弛cnt+1次
for(int k = 1; k <= cnt+1; k++) {
minDist_copy = minDist; //获取上一次计算的结果
for(const vector<int> &edge : edges) { //遍历每一条边
int from = edge[0];
int to = edge[1];
int value = edge[2];
//注意使用minDist_copy来计算minDist
if(minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + value) {
minDist[to] = minDist_copy[from] + value;
}
}
}
if(minDist[dst] == INT_MAX) cout << "unreachable" << endl;
else cout << minDist[dst] << endl;
return 0;
}97. 小明逛公园
多源最短路Floyd算法模板题（核心思想：DP）
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m, q;
cin >> n >> m;
//grid[i][j][k] = m，表示节点i到j以[1...k]集合中的一个节点为中间节点的最短距离为m
//注意不要初始化为INT_MAX，因为下方算法两数相加时可能会溢出
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(n+1, vector<int>(n+1, 10005)));
int x, y, v;
for(int i = 0; i < m; i++) {
cin >> x >> y >> v;
dp[x][y][0] = v;
dp[y][x][0] = v;
}
//floyd
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j][k] = min(dp[i][j][k-1], dp[i][k][k-1] + dp[k][j][k-1]);
}
}
}
cin >> q;
for(int i = 0; i < q; i++) {
cin >> x >> y;
if(dp[x][y][n] == 10005) cout << -1 << endl;
else cout << dp[x][y][n] << endl;
}
return 0;
}127. 骑士的攻击
A*算法：即有目的地广搜（核心在于启发式函数，来影响队列里元素的排序）
#include<bits/stdc++.h>
using namespace std;
int moves[1001][1001];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int b1, b2;
//F = G + H
//G = 从起点到该节点路径消耗
//H = 该节点到终点的预估消耗
struct Knight{
int x,y;
int g,h,f;
bool operator < (const Knight & k) const{ //重载运算符，从小到大排序
return k.f < f;
}
};
priority_queue<Knight> que;
int Heuristic(const Knight& k) { //欧拉距离
return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); //统一不开根号，可以提高精度
}
void astar(const Knight& k) {
Knight cur, next;
que.push(k);
while(!que.empty()) {
cur = que.top();
que.pop();
if(cur.x == b1 && cur.y == b2) break;
for(int i = 0; i < 8; i++) {
next.x = cur.x + dir[i][0];
next.y = cur.y + dir[i][1];
if(next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) continue;
if(!moves[next.x][next.y]){
moves[next.x][next.y] = moves[cur.x][cur.y] + 1;
// 开始计算F
next.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
next.h = Heuristic(next);
next.f = next.g + next.h;
que.push(next);
}
}
}
}
int main() {
int n, a1, a2;
cin >> n;
while(n--) {
cin >> a1 >> a2 >> b1 >> b2;
memset(moves,0,sizeof(moves));
Knight start;
start.x = a1;
start.y = a2;
start.g = 0;
start.h = Heuristic(start);
start.f = start.g + start.h;
astar(start);
while(!que.empty()) que.pop(); //队列清空
cout << moves[b1][b2] << endl;
}
return 0;
}
评论