圖論整理復習

回溯：

模板：

void backtracking(參數) {if (終止條件) {存放結果;return;}for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {處理節點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結果}
}

77.組合：

給定兩個整數?n?和?k，返回范圍?[1, n]?中所有可能的?k?個數的組合。

你可以按?任何順序?返回答案。

示例 1：

輸入：n = 4, k = 2
輸出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

?主要記憶：橫向為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:

輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
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[x][i] == 1 && !visited[i]) { // 找到x鏈接的且未訪問過的節點visited[i] = true; // 標記為已訪問path.push_back(i); // 遍歷到的節點加入到路徑中來dfs(graph, i, n); // 進入下一層遞歸path.pop_back(); // 回溯，撤銷本節點visited[i] = 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[s][t] = 1;}visited[1] = 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[i].size() - 1; j++) {cout << result[i][j] << " ";}cout << result[i][result[i].size() - 1] << endl;}return 0;
}

547:省份數量

有?n?個城市，其中一些彼此相連，另一些沒有相連。如果城市?a?與城市?b?直接相連，且城市?b?與城市?c?直接相連，那么城市?a?與城市?c?間接相連。

省份?是一組直接或間接相連的城市，組內不含其他沒有相連的城市。

給你一個?n x n?的矩陣?isConnected?，其中?isConnected[i][j] = 1?表示第?i?個城市和第?j?個城市直接相連，而?isConnected[i][j] = 0?表示二者不直接相連。

返回矩陣中?省份?的數量。

示例 1：

輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2

class Solution {
public:// 需要額外添加一個visited矩陣來確定當前遍歷到的點是否已經走過，進行剪枝，提前終止遞歸，作為遞歸停止的條件void dfs(vector<vector<int>>& isConnected, int x, vector<bool>& visited){if(visited[x]){return;}visited[x] = true;for(int i = 0; i < isConnected.size(); i++){if(isConnected[x][i] == 1 && !visited[i]){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[i]){dfs(isConnected, i, visited);res++;}}return res;}
};

200:島嶼數量

給你一個由?'1'（陸地）和?'0'（水）組成的的二維網格，請你計算網格中島嶼的數量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設該網格的四條邊均被水包圍。

示例 1：

輸入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
輸出：1

class Solution {
public:// 定義四個方向的偏移量：下、右、上、左int opt[4][2] = {{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[0].size() || visited[i][j] || grid[i][j] == '0'){return;}visited[i][j] = true;  // 標記當前陸地為已訪問for(int a = 0; a < 4; a++){  // 遍歷四個方向int x = i + opt[a][0];   // 計算新坐標xint y = j + opt[a][1];   // 計算新坐標ydfs(grid, visited, x, y);  // 遞歸探索相鄰位置}}// 主函數：計算島嶼數量// 參數：grid-二維字符網格// 返回值：島嶼總數int numIslands(vector<vector<char>>& grid) {// 處理空輸入情況if (grid.empty() || grid[0].empty()) return 0;int n = grid.size(), m = grid[0].size();  // n:行數, m:列數int res = 0;  // 島嶼計數器// 創建訪問標記數組，初始化為falsevector<vector<bool>> visited(n, vector<bool>(m, false));// 遍歷整個網格for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){// 發現未訪問的陸地if(!visited[i][j] && grid[i][j] == '1'){res++;  // 島嶼數量加1dfs(grid, visited, i, j);  // DFS標記整個島嶼}}}return res;  // 返回總島嶼數}
};

695:島嶼的最大面積

給你一個大小為?m x n?的二進制矩陣?grid?。

島嶼?是由一些相鄰的?1?(代表土地) 構成的組合，這里的「相鄰」要求兩個?1?必須在?水平或者豎直的四個方向上?相鄰。你可以假設?grid?的四個邊緣都被?0（代表水）包圍著。

島嶼的面積是島上值為?1?的單元格的數目。

計算并返回?grid?中最大的島嶼面積。如果沒有島嶼，則返回面積為?0?。

示例 1：

輸入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
輸出：6
解釋：答案不應該是 11 ，因為島嶼只能包含水平或垂直這四個方向上的 1 。

class Solution {
public:// 定義四個方向的偏移量數組：下、上、右、左int opt[4][2] = {{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[0].size() || visited[i][j] || grid[i][j] == 0) {return;  // 滿足任一條件則停止當前分支的探索}visited[i][j] = true;  // 標記當前位置為已訪問s++;  // 當前島嶼面積增加1// 遍歷四個方向（下、上、右、左）for (int a = 0; a < 4; a++) {int x = i + opt[a][0];  // 計算新坐標的行號int y = j + opt[a][1];  // 計算新坐標的列號dfs(grid, visited, x, y, s);  // 遞歸探索相鄰位置}}// 主函數：計算網格中最大島嶼的面積// 參數：// grid - 二維整數網格，1表示陸地，0表示水域// 返回值：最大島嶼的面積（相連的1的總數）int maxAreaOfIsland(vector<vector<int>>& grid) {// 檢查輸入是否為空，若為空則返回0if (grid.empty() || grid[0].empty()) return 0;int rows = grid.size();     // 獲取網格的行數int cols = grid[0].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[i][j] == 1 && !visited[i][j]) {int s = 0;  // 初始化當前島嶼面積為0dfs(grid, visited, i, j, s);  // 通過DFS計算當前島嶼的面積res = max(res, s);  // 更新最大島嶼面積}}}return res;  // 返回最大島嶼面積}
};

?463:島嶼的周長

給定一個?row x col?的二維網格地圖?grid?，其中：grid[i][j] = 1?表示陸地，?grid[i][j] = 0?表示水域。

網格中的格子?水平和垂直?方向相連（對角線方向不相連）。整個網格被水完全包圍，但其中恰好有一個島嶼（或者說，一個或多個表示陸地的格子相連組成的島嶼）。

島嶼中沒有“湖”（“湖” 指水域在島嶼內部且不和島嶼周圍的水相連）。格子是邊長為 1 的正方形。網格為長方形，且寬度和高度均不超過 100 。計算這個島嶼的周長。

示例 1：

輸入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
輸出：16
解釋：它的周長是上面圖片中的 16 個黃色的邊

class Solution {
public:// 定義四個方向的偏移量數組：下、上、右、左int opt[4][2] = {{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[0].size() || visited[i][j] || grid[i][j] == 0) {return;  // 滿足任一條件則停止當前分支的探索}visited[i][j] = true;  // 標記當前位置為已訪問// 遍歷四個方向，檢查每個相鄰位置for (int a = 0; a < 4; a++) {int x = i + opt[a][0];  // 計算相鄰位置的行號int y = j + opt[a][1];  // 計算相鄰位置的列號// 檢查相鄰位置是否是邊界或水域if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == 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[0].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[i][j] == 1 && !visited[i][j]) {dfs(grid, visited, i, j, res);  // 通過DFS計算當前島嶼的周長// 注意：這里假設只有一個島嶼，若有多個島嶼，res會累加所有周長}}}return res;  // 返回總周長}
};

?2658:網格圖中魚的最大數目

給你一個下標從?0?開始大小為?m x n?的二維整數數組?grid?，其中下標在?(r, c)?處的整數表示：

如果?grid[r][c] = 0?，那么它是一塊?陸地?。
如果?grid[r][c] > 0?，那么它是一塊?水域?，且包含?grid[r][c]?條魚。

一位漁夫可以從任意?水域?格子?(r, c)?出發，然后執行以下操作任意次：

捕撈格子?(r, c)?處所有的魚，或者
移動到相鄰的?水域?格子。

請你返回漁夫最優策略下，?最多?可以捕撈多少條魚。如果沒有水域格子，請你返回?0?。

格子?(r, c)?相鄰?的格子為?(r, c + 1)?，(r, c - 1)?，(r + 1, c)?和?(r - 1, c)?，前提是相鄰格子在網格圖內。

示例 1：

輸入：grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
輸出：7
解釋：漁夫可以從格子 (1,3) 出發，捕撈 3 條魚，然后移動到格子 (2,3)?，捕撈 4 條魚。

class Solution {
public:// 定義四個方向的偏移量數組：下、上、右、左，用于探索相鄰格子int opt[4][2] = {{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[i][j] == 0）// 3. 當前格子已訪問過if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0 || visited[i][j]) {return;  // 滿足任一條件則停止當前分支的探索}visited[i][j] = true;  // 標記當前格子為已訪問fishes += grid[i][j];  // 將當前格子的魚數累加到fishes中// 遍歷四個方向（下、上、右、左）for (int a = 0; a < 4; a++) {int x = i + opt[a][0];  // 計算相鄰格子的行號int y = j + opt[a][1];  // 計算相鄰格子的列號dfs(grid, visited, x, y, fishes);  // 遞歸探索相鄰格子}}// 主函數：找到網格中單一連通區域的最大魚數// 參數：// grid - 二維整數網格，0表示水域，大于0表示魚的數量// 返回值：最大連通區域的魚數總和int findMaxFish(vector<vector<int>>& grid) {int res = 0;  // 記錄最大魚數，初始化為0int fishes = 0;  // 記錄當前連通區域的魚數int m = grid.size();     // 獲取網格的行數int n = grid[0].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[i][j] >= 0 && !visited[i][j]) {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[row][col]?的?連通分量的邊界?進行著色。

并返回最終的網格?grid?。

示例 1：

輸入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
輸出：[[3,3],[3,2]]

示例 2：

輸入：grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
輸出：[[1,3,3],[2,3,3]]

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[i][j] != cur || visited[i][j]) {return;}visited[i][j] = true;  // 標記當前格子為已訪問bool isBorder = false;  // 使用局部變量判斷是否為邊界// 檢查四個方向是否為邊界if (i == 0 || i == m-1 || j == 0 || j == n-1) {  // 網格邊緣isBorder = true;} else {  // 內部格子，檢查相鄰顏色if (grid[i+1][j] != cur || grid[i-1][j] != cur || grid[i][j+1] != cur || grid[i][j-1] != cur) {isBorder = true;}}if (isBorder) {is_border[i][j] = 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[0].empty() || row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size()) {return grid;}int m = grid.size();    // 行數int n = grid[0].size(); // 列數vector<vector<bool>> visited(m, vector<bool>(n, false));  // 訪問標記vector<vector<bool>> is_border(m, vector<bool>(n, false)); // 邊界標記int cur = grid[row][col];  // 起始格子的顏色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[i][j]) {  // 簡化為直接判斷布爾值grid[i][j] = 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[u].push_back(v);adj[v].push_back(u); // 如果是有向圖，注釋掉這一行}// BFS實現void bfs(int start) {// 標記訪問數組vector<bool> visited(V, false);// 記錄距離的數組vector<int> distance(V, -1);// 創建隊列queue<int> q;// 從起點開始visited[start] = true;distance[start] = 0;q.push(start);while (!q.empty()) {// 取出隊首節點int current = q.front();q.pop();// 輸出當前節點（可以根據需求修改）cout << "Visiting node " << current << " at distance " << distance[current] << endl;// 遍歷當前節點的所有鄰接節點for (vector<int>::iterator it = adj[current].begin(); it != adj[current].end(); ++it) {int neighbor = *it;if (!visited[neighbor]) {visited[neighbor] = true;distance[neighbor] = distance[current] + 1;q.push(neighbor);}}}}
};

?鄰接矩陣存儲圖：

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for std::pairusing namespace std; // 如果不用這個，需要在pair前加std::int dir[4][2] = {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[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(pair<int, int>(nextx, nexty)); // 隊列添加該節點visited[nextx][nexty] = 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[i] = [ui, vi]?表示新建一條從城市?ui?到城市?vi?的單向道路。每次查詢后，你需要找到從城市?0?到城市?n - 1?的最短路徑的長度。

返回一個數組?answer，對于范圍?[0, queries.length - 1]?中的每個?i，answer[i]?是處理完前?i + 1?個查詢后，從城市?0?到城市?n - 1?的最短路徑的長度。

示例 1：

輸入：?n = 5, queries = [[2, 4], [0, 2], [0, 4]]

輸出：?[3, 2, 1]

解釋：

新增一條從 2 到 4 的道路后，從 0 到 4 的最短路徑長度為 3。

新增一條從 0 到 2 的道路后，從 0 到 4 的最短路徑長度為 2。

新增一條從 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[x] = true;while(!que.empty()){int cur = que.front();  que.pop();for(int i = 0; i < graph[cur].size(); i++){int next = graph[cur][i];if(!visited[next]){dis[next] = dis[cur] + 1;visited[next] = 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[i].push_back(i + 1);}for(int i = 0; i < queries.size(); i++){int x = queries[i][0];int y = queries[i][1];graph[x].push_back(y);for(int i = 0; i < n; i++){visited[i] = false;dis[i] = 0;}bfs(graph, visited, dis, 0);res[i] = dis[n - 1];}return res;}
};