图论整理复习
回溯：模板：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
} 77.组合：
给定两个整数 n 和 k，返回范围 中所有大概的 k 个数的组合。
你可以按 任何序次 返回答案。
示例 1：
<strong>输入：</strong>n = 4, k = 2
<strong>输出：</strong>
[
,
,
,
,
,
,
] https://i-blog.csdnimg.cn/direct/fea7e0af90b6458d95136ec831a009be.png
主要记忆：横向为for循环控制，纵向遍历为递归控制，在每次递归操作之后要加上回溯的操作，也就是绘图递归前的那一步操作。
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtrack(int n, int k, int sindex){
if(path.size() == k){
res.push_back(path);
return;
}
for(int i = sindex; i <= n; i++){
path.push_back(i);
backtrack(n, k, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtrack(n, k, 1);
return res;
}
}; 216:组合总和
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
[*]只使用数字1到9
[*]每个数字 最多使用一次
返回 所有大概的有效组合的列表 。该列表不能包罗雷同的组合两次，组合可以以任何序次返回。
示例 1:
<strong>输入:</strong> <em><strong>k</strong></em> = 3, <em><strong>n</strong></em> = 7
<strong>输出:</strong> []
<strong>解释:</strong>
1 + 2 + 4 = 7
没有其他符合的组合了。
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
int sum = 0;
void backtrack(int n, int k, int sindex){
if(sum == n && path.size() == k){
res.push_back(path);
return;
}
for(int i = sindex; i <= 9; i++){
path.push_back(i);
sum += i;
backtrack(n, k, i + 1);
sum -= i;
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtrack(n, k, 1);
return res;
}
};
DFS：
模板：
记载每一个符合的区域，需要用到回溯的头脑，在每一次进入递归回溯后需要进行复位操作：
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径
vector<bool> visited; // 标记节点是否被访问过
void dfs(const vector<vector<int> >& graph, int x, int n) {
// 停止搜索的条件：
// 1. 搜索到了已经搜索过的节点（在path中的节点）
// 2. 搜索到了不符合需求的节点（这里不需要特别判断，因为for循环会自动处理无出边的情况）
if (x == n) { // 找到符合条件的一条路径
result.push_back(path);
return;
}
for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
if (graph == 1 && !visited) { // 找到x链接的且未访问过的节点
visited = true; // 标记为已访问
path.push_back(i); // 遍历到的节点加入到路径中来
dfs(graph, i, n); // 进入下一层递归
path.pop_back(); // 回溯，撤销本节点
visited = false; // 回溯，取消访问标记
}
}
}
int main() {
int n, m, s, t;
cin >> n >> m;
// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<vector<int> > graph(n + 1, vector<int>(n + 1, 0));
visited.resize(n + 1, false); // 初始化visited数组
while (m--) {
cin >> s >> t;
// 使用邻接矩阵 表示无向图，1 表示 s 与 t 是相连的
graph = 1;
}
visited = true; // 起点标记为已访问
path.push_back(1); // 无论什么路径已经是从1节点出发
dfs(graph, 1, n); // 开始遍历
// 输出结果
if (result.size() == 0) {
cout << -1 << endl;
}
for (size_t i = 0; i < result.size(); i++) {
for (size_t j = 0; j < result.size() - 1; j++) {
cout << result << " ";
}
cout << result.size() - 1] << endl;
}
return 0;
} 547:省份数目
有 n 个城市，其中一些彼此相连，另一些没有相连。假如城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected = 1 表现第 i 个城市和第 j 个城市直接相连，而 isConnected = 0 表现二者不直接相连。
返回矩阵中 省份 的数目。
示例 1：
https://i-blog.csdnimg.cn/img_convert/012340e438d8e8b5bad9e7424d39373a.jpeg
<strong>输入：</strong>isConnected = [,,]
<strong>输出：</strong>2 class Solution {
public:
// 需要额外添加一个visited矩阵来确定当前遍历到的点是否已经走过，进行剪枝，提前终止递归，作为递归停止的条件
void dfs(vector<vector<int>>& isConnected, int x, vector<bool>& visited){
if(visited){
return;
}
visited = true;
for(int i = 0; i < isConnected.size(); i++){
if(isConnected == 1 && !visited){
dfs(isConnected, i, visited);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
vector<bool> visited(isConnected.size(), false);
int res = 0;
for(int i = 0; i < isConnected.size(); i++){
if(!visited){
dfs(isConnected, i, visited);
res++;
}
}
return res;
}
}; 200:岛屿数目
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你盘算网格中岛屿的数目。
岛屿总是被水包围，而且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地毗连形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
<strong>输入：</strong>grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
<strong>输出：</strong>1 class Solution {
public:
// 定义四个方向的偏移量：下、右、上、左
int opt = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
// DFS函数：深度优先搜索标记相连的陆地
// 参数：grid-网格，visited-访问标记，i,j-当前坐标
void dfs(const vector<vector<char>>& grid, vector<vector<bool>>& visited, int i, int j){
// 终止条件：越界、已访问过、或遇到水域('0')
if(i < 0 || j < 0 || i >= grid.size() || j >= grid.size() ||
visited || grid == '0'){
return;
}
visited = true;// 标记当前陆地为已访问
for(int a = 0; a < 4; a++){// 遍历四个方向
int x = i + opt; // 计算新坐标x
int y = j + opt; // 计算新坐标y
dfs(grid, visited, x, y);// 递归探索相邻位置
}
}
// 主函数：计算岛屿数量
// 参数：grid-二维字符网格
// 返回值：岛屿总数
int numIslands(vector<vector<char>>& grid) {
// 处理空输入情况
if (grid.empty() || grid.empty()) return 0;
int n = grid.size(), m = grid.size();// n:行数, m:列数
int res = 0;// 岛屿计数器
// 创建访问标记数组，初始化为false
vector<vector<bool>> visited(n, vector<bool>(m, false));
// 遍历整个网格
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
// 发现未访问的陆地
if(!visited && grid == '1'){
res++;// 岛屿数量加1
dfs(grid, visited, i, j);// DFS标记整个岛屿
}
}
}
return res;// 返回总岛屿数
}
}; 695:岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平大概竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
盘算并返回 grid 中最大的岛屿面积。假如没有岛屿，则返回面积为 0 。
示例 1：
https://i-blog.csdnimg.cn/img_convert/3453fe59c8b58f646e05c52801259ae7.jpeg
<strong>输入：</strong>grid = [,,,,,,,]
<strong>输出：</strong>6
<strong>解释：</strong>答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。 class Solution {
public:
// 定义四个方向的偏移量数组：下、上、右、左
int opt = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// DFS 函数：深度优先搜索计算岛屿面积
// 参数：
// grid - 输入的二维网格（只读）
// visited - 访问标记数组
// i, j - 当前探索的坐标
// s - 当前岛屿面积（引用传递，以便累加）
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j, int& s) {
// 检查终止条件：
// 1. 坐标越界（i或j超出网格范围）
// 2. 当前位置已访问过
// 3. 当前位置是水域（值为0）
if (i < 0 || j < 0 || i >= grid.size() || j >= grid.size() ||
visited || grid == 0) {
return;// 满足任一条件则停止当前分支的探索
}
visited = true;// 标记当前位置为已访问
s++;// 当前岛屿面积增加1
// 遍历四个方向（下、上、右、左）
for (int a = 0; a < 4; a++) {
int x = i + opt;// 计算新坐标的行号
int y = j + opt;// 计算新坐标的列号
dfs(grid, visited, x, y, s);// 递归探索相邻位置
}
}
// 主函数：计算网格中最大岛屿的面积
// 参数：
// grid - 二维整数网格，1表示陆地，0表示水域
// 返回值：最大岛屿的面积（相连的1的总数）
int maxAreaOfIsland(vector<vector<int>>& grid) {
// 检查输入是否为空，若为空则返回0
if (grid.empty() || grid.empty()) return 0;
int rows = grid.size(); // 获取网格的行数
int cols = grid.size();// 获取网格的列数
int res = 0;// 记录最大岛屿面积
// 创建访问标记数组，初始化所有位置为未访问（false）
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
// 遍历网格的每一个位置
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 如果当前位置是未访问的陆地
if (grid == 1 && !visited) {
int s = 0;// 初始化当前岛屿面积为0
dfs(grid, visited, i, j, s);// 通过DFS计算当前岛屿的面积
res = max(res, s);// 更新最大岛屿面积
}
}
}
return res;// 返回最大岛屿面积
}
}; 463:岛屿的周长
给定一个 row x col 的二维网格地图 grid ，其中：grid = 1 表现陆地， grid = 0 表现水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（大概说，一个或多个表现陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿四周的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。盘算这个岛屿的周长。
示例 1：
https://i-blog.csdnimg.cn/img_convert/531fe06adc1a3f3d8662b781b679a4b2.png
<strong>输入：</strong>grid = [,,,]
<strong>输出：</strong>16
<strong>解释：</strong>它的周长是上面图片中的 16 个黄色的边 class Solution {
public:
// 定义四个方向的偏移量数组：下、上、右、左
int opt = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// DFS 函数：深度优先搜索计算岛屿周长
// 参数：
// grid - 输入的二维网格（只读），1表示陆地，0表示水域
// visited - 访问标记数组，用于避免重复访问
// i, j - 当前探索的坐标
// c - 周长计数器（引用传递，以便累加）
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j, int& c) {
// 检查终止条件：
// 1. 坐标越界（i或j超出网格范围）
// 2. 当前位置已访问过
// 3. 当前位置是水域（值为0）
if (i < 0 || j < 0 || i >= grid.size() || j >= grid.size() ||
visited || grid == 0) {
return;// 满足任一条件则停止当前分支的探索
}
visited = true;// 标记当前位置为已访问
// 遍历四个方向，检查每个相邻位置
for (int a = 0; a < 4; a++) {
int x = i + opt;// 计算相邻位置的行号
int y = j + opt;// 计算相邻位置的列号
// 检查相邻位置是否是边界或水域
if (x < 0 || y < 0 || x >= grid.size() || y >= grid.size() || grid == 0) {
c++;// 如果是边界或水域，周长加1
}
// 递归探索相邻位置（即使是边界或水域也会被上面的if拦截）
dfs(grid, visited, x, y, c);
}
}
// 主函数：计算岛屿的总周长
// 参数：
// grid - 二维整数网格，1表示陆地，0表示水域
// 返回值：所有岛屿的总周长
int islandPerimeter(vector<vector<int>>& grid) {
int res = 0;// 初始化周长结果
int m = grid.size(); // 获取网格的行数
int n = grid.size();// 获取网格的列数
// 创建访问标记数组，初始化所有位置为未访问（false）
vector<vector<bool>> visited(m, vector<bool>(n, false));
// 遍历网格的每一个位置
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果当前位置是未访问的陆地
if (grid == 1 && !visited) {
dfs(grid, visited, i, j, res);// 通过DFS计算当前岛屿的周长
// 注意：这里假设只有一个岛屿，若有多个岛屿，res会累加所有周长
}
}
}
return res;// 返回总周长
}
}; 2658:网格图中鱼的最大数目
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表现：
[*]假如 grid = 0 ，那么它是一块 陆地 。
[*]假如 grid > 0 ，那么它是一块 水域 ，且包罗 grid 条鱼。
一位渔夫可以从任意 水域 格子 (r, c) 出发，然后执行以下操作任意次：
[*]捕捞格子 (r, c) 地方有的鱼，大概
[*]移动到相邻的 水域 格子。
请你返回渔夫最优计谋下， 最多 可以捕捞多少条鱼。假如没有水域格子，请你返回 0 。
格子 (r, c) 相邻 的格子为 (r, c + 1) ，(r, c - 1) ，(r + 1, c) 和 (r - 1, c) ，条件是相邻格子在网格图内。
示例 1：
https://i-blog.csdnimg.cn/img_convert/38f40cb042d5ed4e1da0236f127348cf.png
<strong>输入：</strong>grid = [,,,]
<strong>输出：</strong>7
<strong>解释：</strong>渔夫可以从格子 (1,3) 出发，捕捞 3 条鱼，然后移动到格子 (2,3) ，捕捞 4 条鱼。 class Solution {
public:
// 定义四个方向的偏移量数组：下、上、右、左，用于探索相邻格子
int opt = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// DFS 函数：深度优先搜索计算单一连通区域的鱼数
// 参数：
// grid - 输入的二维网格（只读），0表示水域，大于0表示鱼的数量
// visited - 访问标记数组，用于记录已访问的格子
// i, j - 当前探索的网格坐标
// fishes - 当前连通区域的鱼数总和（引用传递，以便累加）
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j, int& fishes) {
// 检查终止条件：
// 1. 坐标越界（i或j超出网格范围）
// 2. 当前格子是水域（grid == 0）
// 3. 当前格子已访问过
if (i < 0 || j < 0 || i >= grid.size() || j >= grid.size() ||
grid == 0 || visited) {
return;// 满足任一条件则停止当前分支的探索
}
visited = true;// 标记当前格子为已访问
fishes += grid;// 将当前格子的鱼数累加到fishes中
// 遍历四个方向（下、上、右、左）
for (int a = 0; a < 4; a++) {
int x = i + opt;// 计算相邻格子的行号
int y = j + opt;// 计算相邻格子的列号
dfs(grid, visited, x, y, fishes);// 递归探索相邻格子
}
}
// 主函数：找到网格中单一连通区域的最大鱼数
// 参数：
// grid - 二维整数网格，0表示水域，大于0表示鱼的数量
// 返回值：最大连通区域的鱼数总和
int findMaxFish(vector<vector<int>>& grid) {
int res = 0;// 记录最大鱼数，初始化为0
int fishes = 0;// 记录当前连通区域的鱼数
int m = grid.size(); // 获取网格的行数
int n = grid.size();// 获取网格的列数
// 创建访问标记数组，初始化所有格子为未访问（false）
vector<vector<bool>> visited(m, vector<bool>(n, false));
// 遍历网格的每一个格子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果当前格子有鱼（>=0）且未访问
// 注意：这里应改为 > 0，因为0表示水域，但保留原逻辑以匹配代码
if (grid >= 0 && !visited) {
fishes = 0;// 重置当前区域鱼数为0，准备计算新区域
dfs(grid, visited, i, j, fishes);// 通过DFS计算当前连通区域的鱼数
res = max(res, fishes);// 更新最大鱼数
}
}
}
return res;// 返回最大鱼数
}
}; 1034:界限着色
给你一个大小为 m x n 的整数矩阵 grid ，表现一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表现该位置处的网格块的颜色。
假如两个方块在任意 4 个方向上相邻，则称它们 相邻 。
假如两个方块具有雷同的颜色且相邻，它们则属于同一个 连通分量 。
连通分量的界限 是指连通分量中满足下述条件之一的所有网格块：
[*]在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
[*]在网格的界限上（第一行/列或最后一行/列）
请你使用指定颜色 color 为所有包罗网格块 grid 的 连通分量的界限 进行着色。
并返回最终的网格 grid 。
示例 1：
<strong>输入：</strong>grid = [,], row = 0, col = 0, color = 3
<strong>输出：</strong>[,] 示例 2：
<strong>输入：</strong>grid = [,], row = 0, col = 1, color = 3
<strong>输出：</strong>[,] class Solution {
public:
// DFS 函数：标记连通区域的边界
void dfs(vector<vector<int>>& grid, int m, int n, int i, int j, const int cur,
vector<vector<bool>>& visited, vector<vector<bool>>& is_border) {
// 终止条件：越界、颜色不同或已访问
if (i < 0 || j < 0 || i >= m || j >= n || grid != cur || visited) {
return;
}
visited = true;// 标记当前格子为已访问
bool isBorder = false;// 使用局部变量判断是否为边界
// 检查四个方向是否为边界
if (i == 0 || i == m-1 || j == 0 || j == n-1) {// 网格边缘
isBorder = true;
} else {// 内部格子，检查相邻颜色
if (grid != cur || grid != cur ||
grid != cur || grid != cur) {
isBorder = true;
}
}
if (isBorder) {
is_border = true;// 标记为边界
}
// 显式递归调用四个方向，避免数组索引
dfs(grid, m, n, i+1, j, cur, visited, is_border);
dfs(grid, m, n, i-1, j, cur, visited, is_border);
dfs(grid, m, n, i, j+1, cur, visited, is_border);
dfs(grid, m, n, i, j-1, cur, visited, is_border);
}
// 主函数：给指定连通区域的边界染色
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
// 检查空输入或无效坐标
if (grid.empty() || grid.empty() || row < 0 || row >= grid.size() ||
col < 0 || col >= grid.size()) {
return grid;
}
int m = grid.size(); // 行数
int n = grid.size(); // 列数
vector<vector<bool>> visited(m, vector<bool>(n, false));// 访问标记
vector<vector<bool>> is_border(m, vector<bool>(n, false)); // 边界标记
int cur = grid;// 起始格子的颜色
dfs(grid, m, n, row, col, cur, visited, is_border);// 执行DFS
// 染色边界格子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (is_border) {// 简化为直接判断布尔值
grid = color;
}
}
}
return grid;
}
}; BFS：
借助queue队列实现对当前节点的扩散式搜索：
模板：
毗邻表存储图：
// 图的邻接表表示
class Graph {
private:
int V; // 顶点数
vector<vector<int> > adj; // 邻接表
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
// 添加边（无向图）
void addEdge(int u, int v) {
adj.push_back(v);
adj.push_back(u); // 如果是有向图，注释掉这一行
}
// BFS实现
void bfs(int start) {
// 标记访问数组
vector<bool> visited(V, false);
// 记录距离的数组
vector<int> distance(V, -1);
// 创建队列
queue<int> q;
// 从起点开始
visited = true;
distance = 0;
q.push(start);
while (!q.empty()) {
// 取出队首节点
int current = q.front();
q.pop();
// 输出当前节点（可以根据需求修改）
cout << "Visiting node " << current
<< " at distance " << distance << endl;
// 遍历当前节点的所有邻接节点
for (vector<int>::iterator it = adj.begin();
it != adj.end(); ++it) {
int neighbor = *it;
if (!visited) {
visited = true;
distance = distance + 1;
q.push(neighbor);
}
}
}
}
}; 毗邻矩阵存储图：
#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for std::pair
using namespace std; // 如果不用这个，需要在pair前加std::
int dir = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
void bfs(vector<vector<char> >& grid, vector<vector<bool> >& visited, int x, int y) {
queue<pair<int, int> > que; // 定义队列
que.push(pair<int, int>(x, y)); // 起始节点加入队列
visited = 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;
int nexty = cury + dir; // 获取周边四个方向的坐标
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid.size())
continue; // 坐标越界，跳过
if (!visited) { // 如果节点没被访问过
que.push(pair<int, int>(nextx, nexty)); // 队列添加该节点
visited = true; // 标记为已访问
}
}
}
}
// 测试代码
int main() {
int rows = 3, cols = 3;
vector<vector<char> > grid(rows, vector<char>(cols, '1'));
vector<vector<bool> > visited(rows, vector<bool>(cols, false));
cout << "Starting BFS from (0, 0)" << endl;
bfs(grid, visited, 0, 0);
return 0;
} 3243:新增蹊径后的查询后的最短间隔I
给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向蹊径通往城市 i + 1（ 0 <= i < n - 1）。
queries = 表现新建一条从城市 ui 到城市 vi 的单向蹊径。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
返回一个数组 answer，对于范围 中的每个 i，answer 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。
示例 1：
输入： n = 5, queries = [, , ]
输出：
解释：
https://i-blog.csdnimg.cn/img_convert/2e8eb8852bb41be1eba2cf733c8eae12.jpeg
新增一条从 2 到 4 的蹊径后，从 0 到 4 的最短路径长度为 3。
https://i-blog.csdnimg.cn/img_convert/56461231dadf2a1a0463f816672974b4.jpeg
新增一条从 0 到 2 的蹊径后，从 0 到 4 的最短路径长度为 2。
https://i-blog.csdnimg.cn/img_convert/b2274ad2f103e4789673191065f29bae.jpeg
新增一条从 0 到 4 的蹊径后，从 0 到 4 的最短路径长度为 1。
思绪：采用毗邻表存储图，套用bfs模板，在每次遍历queries时要重置visited和dis数组：
class Solution {
public:
void bfs(const vector<vector<int>>& graph, vector<bool>& visited, vector<int>& dis, int x){
queue<int> que;
que.push(x);
visited = true;
while(!que.empty()){
int cur = que.front();que.pop();
for(int i = 0; i < graph.size(); i++){
int next = graph;
if(!visited){
dis = dis + 1;
visited = true;
que.push(next);
}else{
continue;
}
}
}
}
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
vector<int> res(queries.size(), 0);
vector<vector<int>> graph(n);
vector<int> dis(n, 0);
vector<bool> visited(n, false);
for(int i = 0; i < n - 1; i++){
graph.push_back(i + 1);
}
for(int i = 0; i < queries.size(); i++){
int x = queries;
int y = queries;
graph.push_back(y);
for(int i = 0; i < n; i++){
visited = false;
dis = 0;
}
bfs(graph, visited, dis, 0);
res = dis;
}
return res;
}
}; 无向图中判断是否存在环路：
方法：
（1）DFS遍历整张图
（2）对于每一个符合要求的节点记载其父节点
（3）在遍历终于到符合要求节点但已经访问过，检查是否为当前递归下的父节点
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]