[{"type":"Heading1","children":[{"text":"图论专题"}],"slateId":"nDG_i6LCPwynBGg9Uv3PJ"},{"type":"Heading2","children":[{"text":"1.遍历"}],"slateId":"3sgVmvZI_YiEaVTf79zij"},{"type":"Heading3","children":[{"text":"1.1 BFS"}],"slateId":"NBjyy5DpkBlcBx5fwj9-w"},{"type":"Heading4","children":[{"text":"1.1.1 邻接矩阵"}],"slateId":"huoTehfTPDTkazJqDjQwx"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"// 邻接矩阵版本\nvoid bfs(vector>& graph, int start, int n) {\n vector visited(n, false);\n queue que;\n \n que.push(start);\n visited[start] = true;\n \n while (!que.empty()) {\n int cur = que.front();\n que.pop();\n \n // 处理当前节点\n cout << cur << \" \";\n \n // 遍历所有邻居\n for (int j = 0; j < n; j++) {\n if (graph[cur][j] && !visited[j]) {\n que.push(j);\n visited[j] = true; // 入队时标记，防止重复入队\n }\n }\n }\n}"}],"slateId":"gszxjjQeCxvSXBKOO26SI"}],"slateId":"QTjIa_usI5QlwC043ZRHX"},{"type":"Heading4","children":[{"text":"1.1.1 邻接表"}],"slateId":"WMU04kPctVSu5rg52hOVJ"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"void bfs(vector>& adj, int start, int n) {\n vector visited(n, false);\n queue que;\n \n que.push(start);\n visited[start] = true;\n \n while (!que.empty()) {\n int cur = que.front();\n que.pop();\n \n for (int neighbor : adj[cur]) {\n if (!visited[neighbor]) {\n que.push(neighbor);\n visited[neighbor] = true;\n }\n }\n }\n}"}],"slateId":"kP1xJd0sKOBqGuMdfZtqs"}],"slateId":"5n4g4Wn36OpO-u6SNdhOF"},{"type":"Heading3","children":[{"text":"2.DFS"}],"slateId":"W6FilvS7JXHnI5rwQde4-"},{"type":"Heading4","children":[{"text":"2.1 递归版本"}],"slateId":"BuM8JBSDRKINbUOsQtaEb"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"void dfs(vector>& graph, vector& visited, int cur, int n) {\n visited[cur] = true;\n \n // 处理当前节点\n cout << cur << \" \";\n \n // 遍历所有邻居\n for (int j = 0; j < n; j++) {\n if (graph[cur][j] && !visited[j]) {\n dfs(graph, visited, j, n);\n }\n }\n}\n\n// 调用\nvoid dfsTraversal(vector>& graph, int n) {\n vector visited(n, false);\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(graph, visited, i, n);\n }\n }\n}"}],"slateId":"7LwcefnnEC7CGRi48l3ZJ"}],"slateId":"JdYsfoMC4JcfxGSBERgp9"},{"type":"Heading4","children":[{"text":"2.2 迭代版本(用栈)"}],"slateId":"nk_jA66ukNXtU7VZwj8Cr"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"void dfs_iterative(vector>& graph, int start, int n) {\n vector visited(n, false);\n stack stk;\n \n stk.push(start);\n \n while (!stk.empty()) {\n int cur = stk.top();\n stk.pop();\n \n if (visited[cur]) continue;\n \n visited[cur] = true;\n cout << cur << \" \";\n \n // 注意：逆序入栈保证顺序（可选）\n for (int j = n - 1; j >= 0; j--) {\n if (graph[cur][j] && !visited[j]) {\n stk.push(j);\n }\n }\n }\n}"}],"slateId":"ICZ_RLS-ieNe9kXBjzRXN"}],"slateId":"4J0EBUGsmxgU6pXKI1SsW"},{"type":"Heading3","children":[{"text":"3.网格(将二维网格看作图)"}],"slateId":"gpaA2aPTDOfYC_9RHSvcI"},{"type":"BulletedList","children":[{"type":"ListItem","children":[{"text":"坐标即节点，相邻即连边"}],"slateId":"JJ7OTHcEWhmeo6RoF1bWM"},{"type":"ListItem","children":[{"text":"不需要显式地构建邻接表，而是通过坐标计算来动态寻找“邻居”"}],"slateId":"YlQQtAlb_I7NqbkI4pRJs"}],"slateId":"THi-DKiGCDQbt-SsyY7Ic"},{"type":"Heading4","children":[{"text":"3.1 DFS版"}],"slateId":"chlfRndgntfV7QOAEKafF"},{"type":"BulletedList","children":[{"type":"ListItem","children":[{"text":"一条路走到黑，撞了南墙再回头"}],"slateId":"QHK6crT7-uBJ-yB7TCI24"}],"slateId":"faeZHbtSmxPYWt3isQ2Ld"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n\nusing namespace std;\n\n// 方向数组：上、下、左、右\nint dx[4] = {-1, 1, 0, 0};\nint dy[4] = {0, 0, -1, 1};\n\nclass DFSSolver {\nprivate:\n int m, n;\n\n // 判断坐标是否在网格范围内\n bool inArea(int x, int y) {\n return x >= 0 && x < m && y >= 0 && y < n;\n }\n\n // DFS 核心递归函数\n void dfs(vector>& grid, int x, int y) {\n // 1. 终止条件（剪枝）\n // 如果越界，或者当前格子不是目标（例如是水 '0'），或者已经访问过，则返回\n if (!inArea(x, y) || grid[x][y] != '1') {\n return;\n }\n\n // 2. 处理当前节点\n // 标记为已访问。\n // 技巧：为了不额外开一个 visited 数组，我们可以直接修改原网格，\n // 比如把陆地 '1' 改成 '2' 或者水 '0'。\n grid[x][y] = '2'; // 标记为已访问\n\n // 3. 递归访问邻居\n // 向四个方向继续探索\n for (int i = 0; i < 4; i++) {\n int nx = x + dx[i];\n int ny = y + dy[i];\n dfs(grid, nx, ny);\n }\n }\n\npublic:\n // 主函数：启动 DFS\n void solve(vector>& grid) {\n m = grid.size();\n if (m == 0) return;\n n = grid[0].size();\n\n // 遍历网格中的每一个点，作为潜在的起点\n for (int i = 0; i < m; i++) {\n for (int j = 0; j < n; j++) {\n // 如果发现一个未被访问的陆地，就开始一次 DFS\n if (grid[i][j] == '1') {\n cout << \"发现新岛屿，从 (\" << i << \", \" << j << \") 开始 DFS...\" << endl;\n dfs(grid, i, j);\n }\n }\n }\n }\n};"}],"slateId":"NUcZvfPcXAFi3uXNZZ3gJ"}],"slateId":"whAI85wAl1RrOmW7k7Fdf"},{"type":"Heading4","children":[{"text":"3.2 BFS版"}],"slateId":"XWONbrHyuKzYGxgeMxUU5"},{"type":"Paragraph","children":[{"text":"-像水波纹一样，一圈一圈向外扩散"}],"slateId":"DGQ73Q6G_q-3-LbcksHFU"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include \n\nusing namespace std;\n\n// 定义坐标结构体，也可以用 pair\nstruct Point {\n int x, y;\n Point(int _x, int _y) : x(_x), y(_y) {}\n};\n\nclass BFSSolver {\nprivate:\n int m, n;\n // 方向数组\n int dx[4] = {-1, 1, 0, 0};\n int dy[4] = {0, 0, -1, 1};\n\n bool inArea(int x, int y) {\n return x >= 0 && x < m && y >= 0 && y < n;\n }\n\npublic:\n // 从指定起点 (startX, startY) 开始 BFS\n void bfs(vector>& grid, int startX, int startY) {\n m = grid.size();\n if (m == 0) return;\n n = grid[0].size();\n\n // 1. 初始化队列\n queue q;\n \n // 2. 起点入队并标记\n q.push(Point(startX, startY));\n grid[startX][startY] = '2'; // 标记为已访问，防止重复入队\n\n while (!q.empty()) {\n // 3. 取出队首元素\n Point curr = q.front();\n q.pop();\n \n int currX = curr.x;\n int currY = curr.y;\n // 这里可以打印当前访问的节点\n // cout << \"访问: (\" << currX << \", \" << currY << \")\" << endl;\n\n // 4. 扩展当前节点的邻居\n for (int i = 0; i < 4; i++) {\n int nextX = currX + dx[i];\n int nextY = currY + dy[i];\n\n // 检查邻居是否合法且是未访问的目标节点\n if (inArea(nextX, nextY) && grid[nextX][nextY] == '1') {\n // 标记并入队\n grid[nextX][nextY] = '2'; // 标记\n q.push(Point(nextX, nextY));\n }\n }\n }\n }\n};"}],"slateId":"IWunk8EvvWKeu_K9nz7os"}],"slateId":"8aELd81f_-mKDFHRH9sIX"},{"type":"Heading2","children":[{"text":"2.连通分量"}],"slateId":"jRU9nzmKy4szVAsb9IDi6"},{"type":"Paragraph","children":[{"text":""},{"type":"Link","href":"https://leetcode.cn/problems/number-of-provinces/","title":"省份数量","children":[{"text":""}],"slateId":"2yjEzjMFCEIuIlvt10Ts7"},{"text":""}],"slateId":"mZCsIDX8W4MEi-px3LYx4"},{"type":"Heading3","children":[{"text":"2.1 DFS版本"}],"slateId":"kSspS7ixUIZRwW2qKlVxf"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"class Solution {\npublic:\n int findCircleNum(vector>& isConnected) {\n int n = isConnected.size();\n vector visited(n, false);\n int provinces = 0;\n \n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(isConnected, visited, i, n);\n provinces++; // 每发现一个未访问的节点，就是一个新连通分量\n }\n }\n return provinces;\n }\n \n void dfs(vector>& isConnected, vector& visited, int i, int n) {\n visited[i] = true;\n for (int j = 0; j < n; j++) {\n if (isConnected[i][j] == 1 && !visited[j]) {\n dfs(isConnected, visited, j, n);\n }\n }\n }\n};"}],"slateId":"3hNHTW9vt9l-_wQTf3YLP"}],"slateId":"tLs1O_UFvQxUqHq9adQ4C"},{"type":"Heading3","children":[{"text":"2.2 BFS版本"}],"slateId":"zAeeEVwQmzWaFkepqgJOu"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"class Solution {\npublic:\n int findCircleNum(vector>& isConnected) {\n int n = isConnected.size();\n vector visited(n, false);\n int provinces = 0;\n \n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n bfs(isConnected, visited, i, n);\n provinces++;\n }\n }\n return provinces;\n }\n \n void bfs(vector>& isConnected, vector& visited, int start, int n) {\n queue q;\n q.push(start);\n visited[start] = true;\n \n while (!q.empty()) {\n int i = q.front(); q.pop();\n for (int j = 0; j < n; j++) {\n if (isConnected[i][j] == 1 && !visited[j]) {\n visited[j] = true;\n q.push(j);\n }\n }\n }\n }\n};"}],"slateId":"B0G0v02iXf4YhOmMbe-r8"}],"slateId":"hIdHr2CpxF5uUMTFSLc9p"},{"type":"Heading3","children":[{"text":"2.3 并查集版本"}],"slateId":"S-DEOwC5HtwGk733Ri_Zz"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"class Solution {\npublic:\n vector parent;\n \n int find(int x) {\n if (parent[x] != x) {\n parent[x] = find(parent[x]); // 路径压缩\n }\n return parent[x];\n }\n \n void unite(int x, int y) {\n parent[find(x)] = find(y);\n }\n \n int findCircleNum(vector>& isConnected) {\n int n = isConnected.size();\n parent.resize(n);\n for (int i = 0; i < n; i++) parent[i] = i;\n \n for (int i = 0; i < n; i++) {\n for (int j = i + 1; j < n; j++) { // 只需看上三角\n if (isConnected[i][j] == 1) {\n unite(i, j);\n }\n }\n }\n \n int provinces = 0;\n for (int i = 0; i < n; i++) {\n if (find(i) == i) provinces++; // 根节点的个数 = 连通分量数\n }\n return provinces;\n }\n};"}],"slateId":"4ZvJnr8yx4Hz6esxf-Rn-"}],"slateId":"O3rGK9avSpqOw9fgTwNpw"},{"type":"Heading2","children":[{"text":"3. BFS拓展"}],"slateId":"1WYWKvIbRZjJ0yxs4w0Cq"},{"type":"Heading3","children":[{"text":"3.1 多源BFS"}],"slateId":"qsyQ3S9XQYATZleWDIlpv"},{"type":"BulletedList","children":[{"type":"ListItem","children":[{"text":"单源 BFS：队列里先放 1 个起点，然后扩散。"}],"slateId":"_dUul7plRMv4C92uo9U1Y"},{"type":"ListItem","children":[{"text":"多源 BFS：队列里先放所有起点，然后一起扩散。"}],"slateId":"fB3pGl3zXBXj9EHenFVhe"}],"slateId":"zOSNoMc_pcSscwN8h_yaF"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n\nusing namespace std;\n\nclass Solution {\npublic:\n int m, n;\n // 方向数组：上、下、左、右\n int dx = {-1, 1, 0, 0};\n int dy = {0, 0, -1, 1};\n\n bool inArea(int x, int y) {\n return x >= 0 && x < m && y >= 0 && y < n;\n }\n\n // 多源 BFS 主函数\n vector> multiSourceBFS(vector>& grid) {\n m = grid.size();\n n = grid.size();\n \n // dist[i][j] 用来存储从任意一个起点到 (i, j) 的最短距离\n // 初始化为 -1，表示尚未访问\n vector> dist(m, vector(n, -1));\n queue> q;\n\n // 1. 【关键步骤】将所有“源点”加入队列，并初始化它们的距离\n for (int i = 0; i < m; i++) {\n for (int j = 0; j < n; j++) {\n // 这里的判断条件根据题目变化\n // 例如：如果是陆地(1)、是腐烂的橘子(2)、是0等\n if (grid[i][j] == 1) { \n q.push({i, j});\n dist[i][j] = 0; // 源点到自己的距离是 0\n }\n }\n }\n\n // 2. 标准的 BFS 扩散过程\n while (!q.empty()) {\n int x = q.front().first;\n int y = q.front().second;\n q.pop();\n\n // 向四个方向扩散\n for (int i = 0; i < 4; i++) {\n int nx = x + dx[i];\n int ny = y + dy[i];\n\n // 检查邻居：在界内且尚未被访问过\n if (inArea(nx, ny) && dist[nx][ny] == -1) {\n // 新位置的距离 = 当前位置距离 + 1\n dist[nx][ny] = dist[x][y] + 1;\n q.push({nx, ny});\n }\n }\n }\n \n return dist;\n }\n};"}],"slateId":"3_iPB9rdz4Ww1AKIE3eIh"}],"slateId":"cjhnvIN7ZeoXtKB0PBtYm"},{"type":"Heading3","children":[{"text":"3.2 三维BFS"}],"slateId":"CButr5wLfl9mIoA4LyGid"},{"type":"Paragraph","children":[{"text":"三维状态 BFS 其实就是给传统的广度优先搜索加了一个“技能冷却”或者“资源背包”的维度。\n简单来说，当我们在走迷宫时，如果多了一个限制条件（比如：只能消除 kk 个障碍、手里有钥匙、或者有毒气值限制），那么单纯记录坐标 (x,y)(x,y) 就不够了。我们需要把状态升级，变成 (x,y,status)(x,y,status) 。"}],"slateId":"＊＊＊VL2ED_TBeMZZj4K8hO"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include \n\nusing namespace std;\n\nclass Solution {\npublic:\n int shortestPath(vector>& grid, int k) {\n int m = grid.size();\n int n = grid[0].size();\n \n // 【优化】如果 k 足够大，直接返回曼哈顿距离\n if (k >= m + n - 2) return m + n - 2;\n\n // 方向数组\n int dx[] = {-1, 1, 0, 0};\n int dy[] = {0, 0, -1, 1};\n\n // --- 核心点 1：三维 Visited 数组 ---\n // visited[r][c][rest] \n // 第三维大小为 k+1，表示剩余 0~k 次机会\n vector>> visited(m, vector>(n, vector(k + 1, false)));\n\n // --- 核心点 2：队列存储三元组 (r, c, rest) ---\n queue> q;\n \n // 初始状态：在 (0,0)，手里有 k 次机会\n q.push({0, 0, k});\n visited[k] = true; // 标记初始状态已访问\n \n int steps = 0;\n \n while (!q.empty()) {\n int size = q.size();\n for (int i = 0; i < size; i++) {\n auto [r, c, rest] = q.front();\n q.pop();\n \n // 到达终点\n if (r == m - 1 && c == n - 1) return steps;\n \n for (int d = 0; d < 4; d++) {\n int nr = r + dx[d];\n int nc = c + dy[d];\n \n if (nr >= 0 && nr < m && nc >= 0 && nc < n) {\n // --- 核心点 3：根据地形决定下一状态的“第三维” ---\n \n // 情况 A：遇到空地 (0) -> 不消耗技能\n if (grid[nr][nc] == 0) {\n // 状态保持不变：rest\n if (!visited[nr][nc][rest]) {\n visited[nr][nc][rest] = true;\n q.push({nr, nc, rest});\n }\n } \n // 情况 B：遇到障碍 (1) -> 消耗技能\n else if (grid[nr][nc] == 1) {\n // 只有技能 > 0 才能走\n if (rest > 0) {\n // 状态变化：rest - 1 (进入下一层维度)\n if (!visited[nr][nc][rest - 1]) {\n visited[nr][nc][rest - 1] = true;\n q.push({nr, nc, rest - 1});\n }\n }\n }\n }\n }\n }\n steps++;\n }\n return -1;\n }\n};"}],"slateId":"wxFSnkLtjayxPd5_y95Az"}],"slateId":"C6hfbFGP58R6i9lmSJxH_"},{"type":"Heading2","children":[{"text":"4.拓扑排序"}],"slateId":"WSq_xVEDsBqKp7d4UouS1"},{"type":"Heading3","children":[{"text":"4.1 Kahn算法(基于入度)"}],"slateId":"-dcXFIxQ3aDU1t8Y5mo56"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include \n\nusing namespace std;\n\n/**\n * 使用 Kahn 算法进行拓扑排序并判断有向图是否有环\n * @param n 节点数量 (假设节点编号为 0 到 n-1)\n * @param edges 边的列表，每个元素 {u, v} 代表一条从 u 指向 v 的有向边\n * @return 如果无环，返回一个拓扑排序序列；如果有环，返回一个空向量\n */\nvector topologicalSortKahn(int n, vector>& edges) {\n // 1. 构建邻接表并计算每个节点的入度\n vector> adj(n);\n vector inDegree(n, 0);\n \n for (const auto& edge : edges) {\n int u = edge;\n int v = edge;\n adj[u].push_back(v); // u -> v\n inDegree[v]++; // v 的入度加 1\n }\n\n // 2. 将所有初始入度为 0 的节点加入队列\n queue q;\n for (int i = 0; i < n; ++i) {\n if (inDegree[i] == 0) {\n q.push(i);\n }\n }\n\n // 3. 开始 BFS 过程\n vector topoOrder;\n while (!q.empty()) {\n int u = q.front();\n q.pop();\n topoOrder.push_back(u); // 将入度为 0 的节点加入结果\n\n // 遍历 u 的所有邻接点 v\n for (int v : adj[u]) {\n inDegree[v]--; // “移除”边 u->v，v 的入度减 1\n if (inDegree[v] == 0) { // 如果 v 的入度变为 0，加入队列\n q.push(v);\n }\n }\n }\n\n // 4. 判断是否有环\n // 如果拓扑序列中的节点数等于总节点数，说明所有节点都被处理，图中无环\n if (topoOrder.size() == n) {\n return topoOrder;\n } else {\n // 否则，说明有节点因为入度始终不为 0 而无法被处理，图中存在环\n return {};\n }\n}\n\nint main() {\n int n = 6;\n // 示例图: 0->1, 0->2, 1->3, 2->3, 3->4, 4->5\n vector> edges = {{0,1}, {0,2}, {1,3}, {2,3}, {3,4}, {4,5}};\n \n vector result = topologicalSortKahn(n, edges);\n\n if (result.empty()) {\n cout << \"图中存在环，无法进行拓扑排序。\" << endl;\n } else {\n cout << \"拓扑排序结果: \";\n for (int node : result) {\n cout << node << \" \";\n }\n cout << endl;\n }\n return 0;\n}"}],"slateId":"QwwqSJugEefl46Z7HkNvE"}],"slateId":"dyXGsb-lA7cio-V3c1fUH"},{"type":"Heading3","children":[{"text":"4.2 DFS 算法(基于节点状态)"}],"slateId":"4svFMAcC1St2D7Ar9-J3b"},{"type":"Paragraph","children":[{"text":"DFS 方法通过深度优先遍历图，并利用节点的三种状态来检测环："}],"slateId":"icMnZy74ZvtOwy4weuvEw"},{"type":"BulletedList","children":[{"type":"ListItem","children":[{"text":"0 (未访问): 节点尚未被处理。"}],"slateId":"hmjy4ZoPb7kjQPiS7qHCd"},{"type":"ListItem","children":[{"text":"1 (访问中): 节点正在当前 DFS 路径上被处理。"}],"slateId":"cwl7K8j5Ye72phoMHuTod"},{"type":"ListItem","children":[{"text":"2 (已访问): 节点及其所有后继节点都已被处理完毕。"}],"slateId":"X94QRqZDsyO_Ip1Tjt_lN"}],"slateId":"n31GRIlAtk0XQ81SKNQCi"},{"type":"Paragraph","children":[{"text":"如果在 DFS 过程中遇到了一个状态为“访问中”的节点，说明存在一条后向边，即图中存在环。"}],"slateId":"nK-V4O7bfVPtRRtOkTFzw"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include // 用于 std::reverse\n\nusing namespace std;\n\n/**\n * 辅助 DFS 函数\n * 注意：这里使用普通函数，通过引用 (&) 捕获外部变量\n */\nvoid dfs(int u, \n const vector>& adj, \n vector& state, \n vector& topoOrder, \n bool& hasCycle) {\n \n // 如果已经发现环，直接返回，不再继续深入\n if (hasCycle) return;\n\n // 1. 标记当前节点为“访问中” (1)\n state[u] = 1;\n\n // 2. 遍历所有邻接点\n for (int v : adj[u]) {\n if (state[v] == 0) {\n // 如果邻居未访问，递归处理\n dfs(v, adj, state, topoOrder, hasCycle);\n } else if (state[v] == 1) {\n // 如果邻居正在访问中（在递归栈里），说明遇到了后向边，即存在环\n hasCycle = true;\n return;\n }\n // 如果 state[v] == 2，说明邻居已处理完毕，直接跳过\n }\n\n // 3. 当前节点的所有后继都处理完了，标记为“已访问” (2)\n state[u] = 2;\n \n // 4. 后序遍历：将节点加入结果集\n topoOrder.push_back(u);\n}\n\n/**\n * 主函数：拓扑排序 & 环检测\n * @param n 节点数量 (0 到 n-1)\n * @param edges 边列表 {u, v} 表示 u -> v\n * @return 拓扑序列，若有环则返回空向量\n */\nvector topologicalSort(int n, vector>& edges) {\n // 1. 构建邻接表\n vector> adj(n);\n for (const auto& edge : edges) {\n adj[edge].push_back(edge);\n }\n\n // 2. 初始化状态数组 (0: 未访问, 1: 访问中, 2: 已访问)\n vector state(n, 0);\n \n vector topoOrder;\n bool hasCycle = false;\n\n // 3. 遍历所有节点，防止图不连通漏掉节点\n for (int i = 0; i < n; ++i) {\n if (state[i] == 0) {\n // 调用普通函数，传入所有必要的引用\n dfs(i, adj, state, topoOrder, hasCycle);\n if (hasCycle) {\n return {}; // 一旦发现环，立即终止并返回空\n }\n }\n }\n\n // 4. DFS 得到的是逆拓扑序（后序遍历），需要反转\n reverse(topoOrder.begin(), topoOrder.end());\n \n return topoOrder;\n}\n\n// --- 测试主函数 ---\nint main() {\n // 测试用例 1: 无环图\n // 0 -> 1 -> 3\n // 2 -> 1\n // 2 -> 4 -> 5\n int n1 = 6;\n vector> edges1 = {{0,1}, {2,1}, {2,4}, {1,3}, {4,5}};\n \n vector res1 = topologicalSort(n1, edges1);\n cout << \"测试 1 (无环): \";\n if (res1.empty()) cout << \"存在环\";\n else { for(int x : res1) cout << x << \" \"; } // 可能输出: 2 0 4 1 5 3 (顺序不唯一)\n cout << endl;\n\n // 测试用例 2: 有环图\n // 0 -> 1 -> 2 -> 0 (环)\n int n2 = 3;\n vector> edges2 = {{0,1}, {1,2}, {2,0}};\n\n vector res2 = topologicalSort(n2, edges2);\n cout << \"测试 2 (有环): \";\n if (res2.empty()) cout << \"存在环\";\n else { for(int x : res2) cout << x << \" \"; }\n cout << endl;\n\n return 0;\n}"}],"slateId":"v1H_MrCXn_VdEsPdJoowc"}],"slateId":"DBJ-JtjsqJ--HhtYfi0_o"},{"type":"Heading3","children":[{"text":"4.3 剥洋葱法(Kahn 算法变种)"}],"slateId":"2wB2o_nz9RdCPYetFz2Nm"},{"type":"Paragraph","children":[{"text":""},{"type":"Link","href":"https://leetcode.cn/problems/minimum-height-trees/description/","title":"最小高度树","children":[{"text":""}],"slateId":"4WL2PeSjVPEl3QHgVPl_S"},{"text":""}],"slateId":"5EaLvDaMJM3urW83Zztkj"},{"type":"Paragraph","children":[{"text":"这套逻辑专门用于解决“寻找图的中心”或“分层处理依赖”这类问题。"}],"slateId":"ArfCGoADjjcdbM4a9LHIS"},{"type":"Paragraph","children":[{"text":"什么是“剥洋葱法”？\n想象这棵树（或图）是一个洋葱："}],"slateId":"fumfao4UDIIqUOJ58XW5t"},{"type":"BulletedList","children":[{"type":"ListItem","children":[{"text":"外层：是所有的叶子节点（入度或度为 1 的节点）。"}],"slateId":"dMqXabPG0VTe6z_OtqHTs"},{"type":"ListItem","children":[{"text":"核心：是我们最终要找的答案（比如最小高度树的根，或者图的最中心）。"}],"slateId":"-rt5__3ZxAojjuFpaAb7p"},{"type":"ListItem","children":[{"text":"动作：我们一层一层地把外层的叶子节点“剥掉”（删除），直到只剩下最核心的 1 个或 2 个节点。"}],"slateId":"zYQEsn6u0U1aAenmrxNXE"}],"slateId":"hWqFwbHoRyJAjHxSlCQ2y"},{"type":"Paragraph","children":[{"text":"这个方法本质上是 Kahn 算法（拓扑排序）的一个变种。"}],"slateId":"wRHdP0ipScfpdDpSgmk9i"},{"type":"Paragraph","children":[{"text":"“剥洋葱法”就是从所有度为 1 的叶子节点开始，通过 BFS 一层层向内删减，最后剩下的就是图的中心。"}],"slateId":"cK2Y_vTw4i-oGL5OUSAn-"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"vector peelOnion(int n, vector>& edges) {\n // 1. 特判：只有一个节点\n if (n == 1) return {0};\n\n // 2. 建图 & 统计度数\n vector> adj(n);\n vector degree(n, 0);\n for (const auto& e : edges) {\n int u = e, v = e;\n adj[u].push_back(v);\n adj[v].push_back(u);\n degree[u]++;\n degree[v]++;\n }\n\n // 3. 初始化队列：将所有度为 1 的叶子节点入队\n queue q;\n for (int i = 0; i < n; ++i) {\n if (degree[i] == 1) {\n q.push(i);\n }\n }\n\n // 4. 剥洋葱过程\n while (n > 2) {\n int size = q.size(); // 当前层的叶子数量\n n -= size; // 剩余节点减少\n\n // 处理当前层的所有叶子\n for (int i = 0; i < size; ++i) {\n int u = q.front();\n q.pop();\n\n // 遍历邻居\n for (int v : adj[u]) {\n degree[v]--; // 邻居度数减 1\n if (degree[v] == 1) {\n q.push(v); // 变成新叶子，入队\n }\n }\n }\n }\n\n // 5. 收集结果\n vector res;\n while (!q.empty()) {\n res.push_back(q.front());\n q.pop();\n }\n return res;\n}"}],"slateId":"f0ds-17km2Uab_XZG_hGj"}],"slateId":"sk7qZMbu0SBb688f4tC3W"},{"type":"Heading2","children":[{"text":"5.最短路径算法"}],"slateId":"3S9uw_0rXR2yNQ-ALn5uv"},{"type":"Heading3","children":[{"text":"5.1 单源最短路径"}],"slateId":"m9JO6z4uvkEp6f-KIoFzT"},{"type":"Heading4","children":[{"text":"5.1.1 无权图最短路径(BFS)"}],"slateId":"VORnPYKGZC2nti9yZCkzq"},{"type":"Paragraph","children":[{"text":"BFS 的核心思想是“层层扩散”，就像水波纹一样从起点一圈圈向外扩展。因为它总是先访问距离起点为 1 的所有节点，再访问距离为 2 的所有节点，以此类推，所以当 BFS 第一次访问到某个节点时，所经过的路径一定是最短的。"}],"slateId":"2W4osO-9nJqiVg5TRI0iM"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include \n#include // for INT_MAX\n\nusing namespace std;\n\n/**\n * 使用 BFS 计算从 start 节点到图中所有其他节点的最短距离\n * @param graph 图的邻接表表示\n * @param start 起始节点\n * @return 一个向量，dist[i] 代表从 start 到 i 的最短距离\n */\nvector bfsShortestDistance(const vector>& graph, int start) {\n int n = graph.size();\n // dist[i] 存储从起点到节点 i 的最短距离\n // 初始化为 -1 表示未访问，也可以初始化为 INT_MAX\n vector dist(n, -1);\n \n queue q;\n \n // 1. 初始化起点\n dist[start] = 0;\n q.push(start);\n \n // 2. BFS 核心循环\n while (!q.empty()) {\n int u = q.front();\n q.pop();\n \n // 3. 遍历当前节点 u 的所有邻居 v\n for (int v : graph[u]) {\n // 如果邻居 v 还没有被访问过\n if (dist[v] == -1) {\n // 到 v 的距离 = 到 u 的距离 + 1\n dist[v] = dist[u] + 1;\n q.push(v);\n }\n }\n }\n \n return dist;\n}\n\nint main() {\n // 示例图：邻接表\n // 0 -- 1 -- 3\n // | |\n // 2 -- 4\n vector> graph = {\n {1, 2}, // 节点 0 连接到 1, 2\n {0, 3, 4}, // 节点 1 连接到 0, 3, 4\n {0, 4}, // 节点 2 连接到 0, 4\n {1}, // 节点 3 连接到 1\n {1, 2} // 节点 4 连接到 1, 2\n };\n \n int start_node = 0;\n vector distances = bfsShortestDistance(graph, start_node);\n \n cout << \"从节点 \" << start_node << \" 到各节点的最短距离：\" << endl;\n for (int i = 0; i < distances.size(); ++i) {\n if (distances[i] == -1) {\n cout << \"到节点 \" << i << \": 不可达\" << endl;\n } else {\n cout << \"到节点 \" << i << \": \" << distances[i] << endl;\n }\n }\n \n return 0;\n}"}],"slateId":"MeaO5qRnTIkaYgrdItV4g"}],"slateId":"zsNL8qFyMIhkB5Eb-NT6z"},{"type":"Heading4","children":[{"text":"5.1.2 Dijkstra算法(无负权边)"}],"slateId":"3eJbVDcmIuRCgVswIcaQP"},{"type":"Paragraph","children":[{"text":"Dijkstra（迪杰斯特拉）算法是图论中解决单源最短路径问题的经典算法。简单来说，它用于在一个所有边权重都为非负数的图中，计算从一个指定的起点到图中所有其他节点的最短距离。\n它的核心思想是贪心策略：从起点开始，每次都选择当前已知距离最短且未被最终确定的节点进行扩展，并更新其邻居节点的距离。"}],"slateId":"f3_UBmaMbozU6u4XFYqUE"},{"type":"Paragraph","children":[{"text":"朴素版本:\n朴素版 Dijkstra 的核心逻辑是：循环 N 次，每次找出一个 dist 最小且未被访问的节点，把它标记为“已访问”，然后更新它的邻居。"}],"slateId":"HhrInTWo44Jz_407WXj7e"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include \n\nusing namespace std;\n\n// 朴素 Dijkstra 算法\n// n: 节点数量\n// graph: 邻接矩阵，graph[u][v] 表示 u->v 的权重，如果不连通则为 INF\n// start: 起点\nvoid dijkstra_naive(int n, vector>& graph, int start) {\n // 1. 初始化距离数组\n vector dist(n, INT_MAX);\n dist[start] = 0;\n\n // 2. 初始化访问标记数组\n vector visited(n, false);\n\n // 3. 主循环：我们要确定 n 个节点的最短距离，所以循环 n 次\n for (int i = 0; i < n; i++) {\n \n // --- 步骤 A: 寻找当前距离最小且未访问的节点 ---\n int u = -1; \n int minDist = INT_MAX;\n \n for (int j = 0; j < n; j++) {\n if (!visited[j] && dist[j] < minDist) {\n minDist = dist[j];\n u = j; // 记录下标\n }\n }\n\n // 如果找不到可达的节点了（剩下的都是 INF），提前退出\n if (u == -1) break;\n\n // --- 步骤 B: 标记该节点为已访问 ---\n visited[u] = true;\n\n // --- 步骤 C: 松弛操作 (更新邻居) ---\n for (int v = 0; v < n; v++) {\n // 如果 u 到 v 有边，且通过 u 到达 v 更近\n if (graph[u][v] != INT_MAX && dist[u] != INT_MAX) {\n if (dist[u] + graph[u][v] < dist[v]) {\n dist[v] = dist[u] + graph[u][v];\n }\n }\n }\n }\n\n // 输出结果\n cout << \"从起点 \" << start << \" 到各点的最短距离：\" << endl;\n for (int i = 0; i < n; i++) {\n if (dist[i] == INT_MAX) cout << i << \": 不可达\" << endl;\n else cout << i << \": \" << dist[i] << endl;\n }\n}\n\nint main() {\n int n = 4;\n // 初始化邻接矩阵，全部设为 INF\n vector> graph(n, vector(n, INT_MAX));\n \n // 对角线设为 0 (自己到自己)\n for(int i=0; iB\n graph = 2; // A->C\n graph = 1; // C->B\n graph = 4; // C->D\n graph = 2; // B->Dsource_group_web_3\n\n dijkstra_naive(n, graph, 0); // 从 A(0) 出发\n\n return 0;\n}"}],"slateId":"OUEnPuW1bSkfythkw_K7U"}],"slateId":"ckO62lph7itXyPrT3zZHD"},{"type":"Paragraph","children":[{"text":"优先级队列版本"}],"slateId":"MZpFyA1RadCxK-eisCG4m"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include \n#include \n\nusing namespace std;\n\n// 定义图的邻接表结构\n// graph[u] 存储了从节点 u 出发的所有边，每条边是一个 {邻居节点, 权重} 的对\ntypedef pair pii; // (weight, node)\n\nvector dijkstra(int n, vector>& graph, int start) {\n // 1. 初始化距离数组，所有距离设为无穷大\n vector dist(n, INT_MAX);\n dist[start] = 0;\n\n // 2. 初始化优先队列（最小堆），存入 (距离, 节点)\n // greater 确保堆顶是距离最小的元素\n priority_queue, greater> pq;\n pq.push({0, start});\n\n // 3. 主循环\n while (!pq.empty()) {\n // 取出当前距离最小的节点\n auto [d, u] = pq.top();\n pq.pop();\n\n // 剪枝：如果取出的距离大于已记录的最短距离，说明是旧数据，跳过\n if (d > dist[u]) {\n continue;\n }\n\n // 遍历当前节点 u 的所有邻居\n for (auto& [weight, v] : graph[u]) {\n // 尝试松弛操作\n // dist[v] = min(dist[v],dist[u] + weight)\n if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {\n dist[v] = dist[u] + weight;\n // 将更新后的状态加入优先队列\n pq.push({dist[v], v});\n }\n }\n }\n\n return dist;\n}\n\nint main() {\n // 示例：构建一个有向图\n // 0 -> 1 (权重4), 0 -> 2 (权重1)\n // 2 -> 1 (权重2), 2 -> 3 (权重5)\n // 1 -> 3 (权重1)\n int n = 4; // 4个节点\n vector> graph(n);\n \n graph.push_back({4, 1});\n graph.push_back({1, 2});\n graph.push_back({2, 1});\n graph.push_back({5, 3});\n graph.push_back({1, 3});source_group_web_10\n\n int start_node = 0;\n vector shortest_distances = dijkstra(n, graph, start_node);\n\n cout << \"从节点 \" << start_node << \" 到各节点的最短距离:\" << endl;\n for (int i = 0; i < n; ++i) {\n if (shortest_distances[i] == INT_MAX)\n cout << i << \": 不可达\" << endl;\n else\n cout << i << \": \" << shortest_distances[i] << endl;\n }\n\n return 0;\n}"}],"slateId":"QBF0CYfbmGkMNReWc2q9b"}],"slateId":"atMl0UDTYY-qsFD9RIXDO"},{"type":"Paragraph","children":[{"text":"Dijkstra 算法的正确性完全依赖于其贪心策略。一旦一个节点 u 从优先队列中弹出，算法就认为已经找到了从起点到 u 的最短路径，并且这个距离不会再被更新。\n这个假设在所有边权重非负的前提下是成立的，因为任何绕远的路径其总权重都不可能比当前路径更短。\n然而，如果图中存在负权边，这个前提就会被打破。可能存在一条经过更多节点的路径，但因为其中包含负权边，其总权重反而更小。Dijkstra 算法由于过早地确定了节点的最短距离，无法处理这种情况，因此会得出错误的结果。\n对于含有负权边的图，需要使用 Bellman-Ford 或 SPFA 等其他算法。\nDijkstra 算法之所以能完美适用于无向图，核心原因在于无向图的本质就是“双向”的有向图，而 Dijkstra 算法本身只关心“能不能走到”以及“代价是多少”，并不关心边的方向性。"}],"slateId":"AD75K2d3DCXpk4zoEtUIf"},{"type":"Paragraph","children":[{"text":"数据结构层面：无向图 = 双向有向图\n在计算机存储中，无向图并不是一种特殊的“魔法结构”，它只是有向图的一种特例。\n对于 Dijkstra 算法来说，它看到的只是“从 A 能去 B”和“从 B 能去 A”这两条独立的路径"}],"slateId":"g7dSr7NjPdyVs-3RV5PC0"},{"type":"Paragraph","children":[{"text":"算法逻辑层面：只看“可达性”与“松弛”\nDijkstra 的核心流程是：取出一个点 uu →→ 遍历它的所有邻居 vv →→ 尝试松弛（更新距离）"}],"slateId":"K18aXJ7IMvxFAyM5dllAa"},{"type":"Paragraph","children":[{"text":"数学原理层面：对称性不影响贪心策略\nDijkstra 依赖的贪心策略（每次选距离最近的点）和松弛操作（"},{"text":"dist[v] = min(dist[v], dist[u] + w)","code":true},{"text":"）依赖于一个前提：边权非负。"}],"slateId":"stEj4WcrRmqhERh0K4Osk"},{"type":"Heading4","children":[{"text":"5.1.3 SPFA算法(允许负权边)"}],"slateId":"n95hWGDSg4r_sVGPQqlMF"},{"type":"Paragraph","children":[{"text":"SPFA（Shortest Path Faster Algorithm）算法，可以理解为 Dijkstra 算法的一个“更灵活”的兄弟，尤其擅长处理带有负权边的图。\n简单来说，它的核心思想是：“只有当一个点的最短距离被更新（变小）了，它才有可能去更新它的邻居。”\n回顾一下 Dijkstra 算法，它使用贪心策略，每次从未确定最短路径的点中选出距离最小的那个，并认为它的最短路径已经确定，之后不再更新。这在边权非负时是完全正确的。\n然而，当图中存在负权边时，这个“一锤定音”的贪心策略就会失效。一条看似较长的路径，可能在后续通过一条负权边，总长度反而变得更短。\nSPFA 就是为了解决这个问题而生的。它允许一个点被多次“松弛”，只要它的最短距离还有可能被优化。"}],"slateId":"qKUlf1kfpyXRvnTs_r2EN"},{"type":"Paragraph","children":[{"text":"SPFA 的核心在于维护一个队列，这个队列里存放的是“距离可能被更新，并需要去更新其邻居”的节点。"}],"slateId":"R-pbX_ckh0HxnrnEL7xOO"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include \n#include \n\nusing namespace std;\n\nconst int INF = 0x3f3f3f3f;\n\n// 边的结构体\nstruct Edge {\n int to; // 目标节点\n int weight; // 边权\n};\n\n// SPFA 算法函数\n// graph: 邻接表，graph[u] 存储了从节点 u 出发的所有边\n// start: 源点\n// n: 节点总数\nvector spfa(vector>& graph, int start, int n) {\n vector dist(n, INF); // dist[i] 表示从 start 到 i 的最短距离\n vector in_queue(n, false); // in_queue[i] 标记节点 i 是否在队列中\n queue q;\n\n // 初始化源点\n dist[start] = 0;\n q.push(start);\n in_queue[start] = true;\n\n while (!q.empty()) {\n int u = q.front();\n q.pop();\n in_queue[u] = false; // 节点 u 出队\n\n // 遍历 u 的所有邻居\n for (const Edge& e : graph[u]) {\n int v = e.to;\n int w = e.weight;\n \n // 尝试松弛\n if (dist[u] + w < dist[v]) {\n dist[v] = dist[u] + w;\n // 如果 v 不在队列中，则将其加入队列\n if (!in_queue[v]) {\n q.push(v);\n in_queue[v] = true;\n }\n }\n }\n }\n\n return dist;\n}"}],"slateId":"vb1u4MDpZgT6w8Z9LBodX"}],"slateId":"LkgawlhyuLHUoi4TXCHMr"},{"type":"Paragraph","children":[{"text":"SPFA 可以处理负权边，但无法处理包含"},{"type":"Span","children":[{"text":"负权环","bold":true}],"slateId":"bEVHElnMIV47CAcFR9ncm"},{"text":"的图。如果图中存在负权环，那么环上的节点可以被无限次松弛，导致算法陷入死循环。\n如何检测负权环？\n可以记录每个节点入队的次数。如果一个节点的入队次数超过了 V-1 次（V 为节点总数），则说明图中存在"},{"type":"Span","children":[{"text":"负权环","bold":true}],"slateId":"1XhmiROuDYOig_dPCg3NH"},{"text":"。"}],"slateId":"l_HSu6X59_DebsaOAGVQG"},{"type":"Heading3","children":[{"text":"5.2 多源最短路径(Floyd算法)"}],"slateId":"RnW8u6uSfqsQCRiLyqudy"},{"type":"Paragraph","children":[{"text":"Floyd 算法，也叫 Floyd-Warshall 算法，是一种用于解决多源最短路径问题的经典算法。简单来说，它能帮你一次性计算出图中任意两个节点之间的最短距离。"}],"slateId":"oCMCCKs3vogP8KmxutNkq"},{"type":"Paragraph","children":[{"text":"核心思想: 动态规划"}],"slateId":"yyB6c-kF7xCtPhT7eSBlq"},{"type":"Paragraph","children":[{"text":"Floyd 算法的本质是动态规划。它的核心思想非常巧妙："}],"slateId":"YTe6KBU0_6lHswev5p0Dl"},{"type":"Paragraph","children":[{"text":"算法通过一个三重循环来实现这个思想。假设我们允许路径经过节点 k，那么从 i 到 j 的最短距离，就有两种可能：\n不经过 k：最短距离就是原来已知的 "},{"text":"dist[i][j]","code":true},{"text":"。\n经过 k：路径被拆分为 i -> k 和 k -> j 两段，总距离为 "},{"text":"dist[i][k] + dist[k][j]","code":true},{"text":"。"}],"slateId":"SUks8mlKCqrCLr35H1PMD"},{"type":"Paragraph","children":[{"text":"Floyd 算法会不断尝试所有可能的中间节点 k，并比较这两种情况，选择距离更短的那个作为新的最短距离。这个过程也被称为松弛。"}],"slateId":"MfPRBtsewvV5Qp703kfi_"},{"type":"Paragraph","children":[{"text":"基础版模板（最常用）"}],"slateId":"VupGGAjt3rUdYYRu2iP4i"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include // 用于 std::min\n\nusing namespace std;\n\n// 定义无穷大，防止加法溢出，通常设为 0x3f3f3f3f 或 INT_MAX/2\nconst int INF = 0x3f3f3f3f; \n\nvoid floyd(vector>& dist) {\n int n = dist.size();\n \n // k 必须在最外层！代表动态规划的阶段（允许经过的中间节点集合）\n for (int k = 0; k < n; k++) {\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n // 剪枝：如果 i->k 或 k->j 不可达，则无需更新\n if (dist[i][k] != INF && dist[k][j] != INF) {\n dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);\n }\n }\n }\n }\n}\n\nint main() {\n // 示例：4 个节点的图\n int n = 4;\n // 初始化邻接矩阵\n vector> dist(n, vector(n, INF));\n\n // 自己到自己距离为 0\n for (int i = 0; i < n; i++) {\n dist[i][i] = 0;\n }\n\n // 模拟输入边：u -> v, 权重 w\n // 0 -> 1, w=5\n dist = 5;\n // 1 -> 2, w=3\n dist = 3;\n // 0 -> 2, w=10 (直接走是 10，经过 1 是 5+3=8，算法会自动更新)\n dist = 10;source_group_web_1\n\n // 执行算法\n floyd(dist);\n\n // 输出结果\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n if (dist[i][j] == INF) cout << \"INF \";\n else cout << dist[i][j] << \" \";\n }\n cout << endl;\n }\n\n return 0;\n}"}],"slateId":"gxA_IPmjQDxJAF5CB_O6O"}],"slateId":"0uNWLPDV04lVsWmoF4fkX"},{"type":"Paragraph","children":[{"text":"进阶版模板（带路径还原）"}],"slateId":"aDmbuWJ0YmIoiebqqpPMo"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n#include \n\nusing namespace std;\n\nconst int INF = 0x3f3f3f3f;\n\n// 打印路径的辅助函数\n// next_node[i][j] 存储的是从 i 到 j 的最短路径上，i 的下一个节点\nvoid print_path(const vector>& next_node, int u, int v) {\n if (next_node[u][v] == -1) {\n cout << \"No path\";\n return;\n }\n \n int curr = u;\n cout << u;\n while (curr != v) {\n curr = next_node[curr][v];\n cout << \" -> \" << curr;\n }\n cout << endl;\n}\n\nvoid floyd_with_path(vector>& dist, vector>& next_node) {\n int n = dist.size();\n\n for (int k = 0; k < n; k++) {\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n if (dist[i][k] != INF && dist[k][j] != INF) {\n if (dist[i][k] + dist[k][j] < dist[i][j]) {\n // 更新距离\n dist[i][j] = dist[i][k] + dist[k][j];\n // 更新路径：从 i 到 j 的下一个点，应该等于从 i 到 k 的下一个点\n next_node[i][j] = next_node[i][k];\n }\n }\n }\n }\n }\n}\n\nint main() {\n int n = 4;\n vector> dist(n, vector(n, INF));\n vector> next_node(n, vector(n, -1)); // 初始化路径矩阵\n\n for (int i = 0; i < n; i++) dist[i][i] = 0;\n\n // 添加边时，同时初始化 next_node\n // 0 -> 1 (w=5)\n dist = 5; next_node = 1;\n // 1 -> 2 (w=3)\n dist = 3; next_node = 2;\n // 0 -> 2 (w=10)\n dist = 10; next_node = 2;source_group_web_2\n\n floyd_with_path(dist, next_node);\n\n // 输出 0 到 2 的最短距离和路径\n cout << \"Distance: \" << dist << endl; // 输出 8\n cout << \"Path: \";\n print_path(next_node, 0, 2); // 输出 0 -> 1 -> 2source_group_web_3\n\n return 0;\n}"}],"slateId":"XmG9ZTMye-kg1BHdVq5Ug"}],"slateId":"MeiO6g36FA27lvhA0SzRb"},{"type":"Heading2","children":[{"text":"6. 并查集"}],"slateId":"qT2sYRGaI_sXSfrJbJmcB"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n\nclass UnionFind {\nprivate:\n std::vector parent; // 父节点数组，parent[i] 存储 i 的父节点\n std::vector rank; // 秩数组，rank[i] 近似表示以 i 为根的树的高度\n int count; // 记录当前连通分量的数量\n\npublic:\n // 构造函数：初始化并查集\n // n: 元素的总数，假设元素索引为 0 到 n-1\n UnionFind(int n) : count(n) {\n parent.resize(n);\n rank.resize(n, 0); // 初始时所有树的高度（秩）为 0\n for (int i = 0; i < n; ++i) {\n parent[i] = i; // 每个元素最初都是一个独立的集合，父节点指向自己\n }\n }\n\n // 查找操作：找到元素 x 所在集合的根节点（代表元）\n // 包含路径压缩优化\n int find(int x) {\n if (parent[x] != x) {\n // 递归查找根节点，并在回溯时将路径上的所有节点直接指向根节点\n parent[x] = find(parent[x]);\n }\n return parent[x];\n }\n\n // 合并操作：将元素 x 和 y 所在的集合合并\n // 包含按秩合并优化\n void unite(int x, int y) {\n int rootX = find(x);\n int rootY = find(y);\n\n if (rootX == rootY) {\n return; // 如果根节点相同，说明已在同一集合，无需合并\n }\n\n // 按秩合并：将秩小的树合并到秩大的树下，以保持树的平衡\n if (rank[rootX] < rank[rootY]) {\n parent[rootX] = rootY;\n } else if (rank[rootX] > rank[rootY]) {\n parent[rootY] = rootX;\n } else {\n // 如果秩相同，任选一个作为新根，并将其秩加一\n parent[rootY] = rootX;\n rank[rootX]++;\n }\n count--; // 合并成功后，连通分量数量减一\n }\n\n // 判断操作：检查元素 x 和 y 是否属于同一个集合\n bool isConnected(int x, int y) {\n return find(x) == find(y);\n }\n\n // 获取当前连通分量的数量\n int getCount() const {\n return count;\n }\n};\n\n// --- 使用示例 ---\nint main() {\n // 模拟一个社交网络，有 6 个用户 (0-5)\n UnionFind uf(6);\n\n std::cout << \"初始连通分量: \" << uf.getCount() << std::endl; // 输出 6\n\n // 用户 0 和 1 成为好友\n uf.unite(0, 1);\n // 用户 1 和 2 成为好友\n uf.unite(1, 2);\n // 用户 3 和 4 成为好友\n uf.unite(3, 4);\n\n std::cout << \"当前连通分量: \" << uf.getCount() << std::endl; // 输出 3\n\n // 判断用户 0 和 2 是否连通（在同一个朋友圈）\n if (uf.isConnected(0, 2)) {\n std::cout << \"用户 0 和 2 是好友关系\" << std::endl;\n }\n\n // 判断用户 0 和 3 是否连通\n if (!uf.isConnected(0, 3)) {\n std::cout << \"用户 0 和 3 不是好友关系\" << std::endl;\n }\n\n // 用户 1 和 3 成为好友，连接了两个朋友圈\n uf.unite(1, 3);\n std::cout << \"最终连通分量: \" << uf.getCount() << std::endl; // 输出 2\n\n return 0;\n}"}],"slateId":"JgyeYp_nb5y8JhLGoB0nE"}],"slateId":"_6Kwa5ze6joUrKR4GLVIr"}]