8.6-8.15力扣图论刷题

【1】133. 克隆图

日期：8.6

1.题目链接：

133. 克隆图 - 力扣（LeetCode）https://leetcode.cn/problems/clone-graph/description/?envType=problem-list-v2&envId=graph2.题目类型：深度优先搜索，广度优先搜索，图，哈希表

3.方法一：深度优先搜索（官方题解）

使用一个哈希表存储所有已被访问和克隆的节点。哈希表中的 key 是原始图中的节点，value 是克隆图中的对应节点。从给定节点开始遍历图。如果某个节点已经被访问过，则返回其克隆图中的对应节点。

如果当前访问的节点不在哈希表中，则创建它的克隆节点并存储在哈希表中。注意：在进入递归之前，必须先创建克隆节点并保存在哈希表中。如果不保证这种顺序，可能会在递归中再次遇到同一个节点，再次遍历该节点时，陷入死循环。

递归调用每个节点的邻接点。每个节点递归调用的次数等于邻接点的数量，每一次调用返回其对应邻接点的克隆节点，最终返回这些克隆邻接点的列表，将其放入对应克隆节点的邻接表中。这样就可以克隆给定的节点和其邻接点。

if (visited.find(node) != visited.end()) { return visited[node];}

作用：如果节点已克隆，直接返回其克隆节点

示例：

当节点A的邻居是B，B的邻居又是A时

克隆A时遇到B，克隆B时又遇到A

此时直接返回已克隆的A节点，打破循环

emplace_back：将克隆的邻居节点加入当前克隆节点的邻居列表

关键代码：

 unordered_map visited; Node* cloneGraph(Node* node){ if(node==nullptr){ return node; } // 检查节点是否已克隆（避免重复克隆和循环递归） if (visited.find(node)!= visited.end()){ return visited[node]; // 直接返回已创建的克隆节点 } // 创建新节点（此时邻居列表为空） Node* cloneNode=new Node(node->val); visited[node] = cloneNode; // 深度优先遍历邻居节点 for(auto& neighbor:node->neighbors){ // 递归克隆邻居，并将克隆节点加入当前节点的邻居列表 cloneNode->neighbors.emplace_back(cloneGraph(neighbor)); } return cloneNode; 

4.方法二：广度优先遍历（半解）

使用一个哈希表 visited 存储所有已被访问和克隆的节点。哈希表中的 key 是原始图中的节点，value 是克隆图中的对应节点。将给定的节点添加到队列。克隆该节点并存储到哈希表中。每次从队列首部取出一个节点，遍历该节点的所有邻接点。如果某个邻接点已被访问，则该邻接点一定在 visited 中，那么从 visited 获得该邻接点，否则创建一个新的节点存储在 visited 中，并将邻接点添加到队列。将克隆的邻接点添加到克隆图对应节点的邻接表中。

关键代码：

 Node* cloneGraph(Node* node){ if(node==nullptr){ return node; } unordered_map visited; queue Q; Q.push(node);  visited[node]=new Node(node->val); while(!Q.empty()){ auto n=Q.front(); // 获取当前处理的原始节点 Q.pop(); // 将已取出的节点移出队列 // 遍历当前节点的所有邻居节点 for(auto& neighbor:n->neighbors){ //检查邻居节点是否已被访问（是否存在于visited中） if (visited.find(neighbor)==visited.end()){  //邻居节点尚未被访问  visited[neighbor]=new Node(neighbor->val); // 将新发现的邻居节点加入队列  Q.push(neighbor); } // emplace_back：将克隆邻居加入当前克隆节点的邻居列表 visited[n]->neighbors.emplace_back(visited[neighbor]); } } return visited[node];

【2】207. 课程表

日期：8.7

1.题目链接：207. 课程表 - 力扣（LeetCode）https://leetcode.cn/problems/course-schedule/description/?envType=problem-list-v2&envId=graph2.题目类型：深度优先搜索，广度优先搜索，图，拓扑排序

3.方法一：深度优先搜索（官方题解）

0：未访问

1：访问中，表示当前DFS路径中

2：已访问，表示该节点及其后代都已处理完毕

关键代码：

public: vector<vector> edges; vector visited;  bool valid=true; void dfs(int u) { visited[u]=1; // 节点为\"访问中\"  // 遍历所有邻居 for(int v:edges[u]){ // 情况1：邻居节点未访问 if (visited[v] == 0) { dfs(v);  if (!valid) return; } // 情况2：邻居节点正在当前路径中被访问 else if(visited[v]==1) { valid = false; // 发现环 return;  } // 情况3：邻居节点已完全访问，无需处理 } visited[u]=2; // 当前节点处理完成，标记为\"已访问\" } bool canFinish(int numCourses, vector<vector>& prerequisites) { edges.resize(numCourses); // 创建邻接表 visited.resize(numCourses); // 创建访问状态数组 // 构建图的邻接表 for(const auto& info:prerequisites){ // info[1] → info[0] : 先修课程 → 目标课程 edges[info[1]].push_back(info[0]); } // 遍历所有节点进行DFS for(int i=0;i<numCourses&&valid;++i){ if(!visited[i]){ dfs(i);  } } return valid; }

4.方法二：广度优先搜索（半解）

在广度优先搜索的每一步中，取出队首的节点 u：

将 u 放入答案中；移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么就将 v 放入队列中。

关键代码：

public: vector<vector> edges; vector indeg;  bool canFinish(int numCourses,vector<vector>& prerequisites) { edges.resize(numCourses); indeg.resize(numCourses); // 设置入度表大小 // 构建图结构和入度表 for (const auto& info:prerequisites){ // info[1] → info[0] : 先修课程info[1]指向目标课程info[0] edges[info[1]].push_back(info[0]);  ++indeg[info[0]];  // 目标课程入度+1 } // 初始化BFS队列 queue q; for(int i=0;i<numCourses;++i){  if(indeg[i]==0){ q.push(i); } } // BFS拓扑排序 int visited=0; while(!q.empty()){ ++visited; int u=q.front(); // 获取队首节点 q.pop(); // 处理当前节点的所有邻居 for (int v: edges[u]){ // 邻居节点入度-1 --indeg[v]; if (indeg[v]==0){  q.push(v); } } } return visited==numCourses;

【3】210. 课程表 II

日期：8.8

1.题目链接：210. 课程表 II - 力扣（LeetCode）https://leetcode.cn/problems/course-schedule-ii/description/?envType=problem-list-v2&envId=graph2.题目类型：深度优先搜索，广度优先搜索，图，拓扑排序

3.方法一：深度优先搜索（一次题解）

v 为「未搜索」：开始搜索 v，待搜索完成回溯到 u；v 为「搜索中」：找到了图中的一个环，因此是不存在拓扑排序的；v 为「已完成」：v 已经在栈中了，而 u 还不在栈中，因此 u 无论何时入栈都不会影响到 (u,v) 之前的拓扑关系，以及不用进行任何操作。

关键代码：

 for (const auto& info:prerequisites){ edges[info[1]].push_back(info[0]); } for(int i=0;i<numCourses&&valid;++i){ if(!visited[i]){ dfs(i); } } if(!valid){ return {}; } // 下标 0 为栈底，需要将数组反序输出 reverse(result.begin(),result.end()); return result;

4.方法一：广度优先搜索（一次题解）

入度表(indeg)：记录每个节点的入度数（依赖课程数量）

BFS队列：处理入度为0的节点（无依赖的课程）

拓扑排序：按依赖顺序依次处理节点

环检测：若排序后仍有节点未被访问，说明存在环

关键代码:

 while (!q.empty()){ int u=q.front(); q.pop(); result.push_back(u); for(int v: edges[u]){ --indeg[v]; if (indeg[v]==0) {  q.push(v); } } }

【4】851. 喧闹和富有

日期：8.9

1.题目链接：851. 喧闹和富有 - 力扣（LeetCode）https://leetcode.cn/problems/loud-and-rich/description/?envType=problem-list-v2&envId=graph2.题目类型：深度优先搜索，图，拓扑排序

3.方法一：深度优先搜索（半解）

根据 richer 构建一张有向图：把人看成点，如果 ai 比 bi更有钱，那么就从 bi向 ai连一条有向边。由于题目保证 richer 中所给出的数据逻辑自恰，得到的是一张有向无环图。因此从图上任意一点（设为 x）出发，沿着有向边所能访问到的点，都比 x 更有钱。

遍历所有人：图可能不连通（存在多个财富群体），最富有的人没有出边，需要主动处理

关键代码：

 int n=quiet.size(); vector<vector> g(n); for(auto &r:richer){ // r[0]比r[1]富有 → 添加边：r[1] -> r[0] g[r[1]].emplace_back(r[0]); } vector ans(n, -1); function dfs=[&](int x){ // 如果已计算过，直接返回 if(ans[x]!=-1){ return; } ans[x]=x;  for(int y:g[x]){ // 递归处理更富有的人 dfs(y); // 比较并更新最安静的人 if(quiet[ans[y]]<quiet[ans[x]]){  ans[x]=ans[y]; } } }; // 对每个人执行DFS for(int i=0;i<n;++i){ dfs(i); } return ans;

4.方法二：拓扑排序（半解）

可以将方法一中的图的边全部反向，即如果 ai比 bi更有钱，从 ai向 bi连一条有向边。得到的是一张有向无环图，因此从图上任意一点（设为 x）出发，沿着有向边所能访问到的点，拥有的钱都比 x 少。这意味着可以在计算出 answer[x] 后，用 answer[x] 去更新 x 所能访问到的点的 answer 值。

关键代码：

 vector<vector> g(n); // 入度数组：记录每个人的入度（有多少人比他富） vector inDeg(n, 0);  // 构建图和入度表 for(auto& r:richer){ g[r[0]].emplace_back(r[1]); // 富人r[0]指向穷人r[1] ++inDeg[r[1]];  // 穷人r[1]的入度+1 } vector ans(n); iota(ans.begin(), ans.end(), 0); // 填充0,1,2,...,n-1 queue q; // 将入度为0的人（最富有的人）入队 for (int i = 0; i < n; ++i) { if (inDeg[i] == 0) { q.emplace(i); } } // BFS拓扑排序 while(!q.empty()){ int x=q.front(); q.pop(); for(int y : g[x]){ //如果x的最优解比y当前的最优解更安静 if(quiet[ans[x]]<quiet[ans[y]]){  ans[y]=ans[x];  } // 减少y的入度，若入度为0则入队 if(--inDeg[y]==0){  q.emplace(y); } } }

【5】997. 找到小镇的法官

日期：8.10

1.题目链接：997. 找到小镇的法官 - 力扣（LeetCode）https://leetcode.cn/problems/find-the-town-judge/description/?envType=problem-list-v2&envId=graph2.题目类型：图，数组，哈希表

3.方法：计算各节点的入度和出度（一次题解）

题干描述了一个有向图。每个人是图的节点，trust 的元素 trust[i] 是图的有向边，从 trust[i][0] 指向 trust[i][1]。可以遍历 trust，统计每个节点的入度和出度，存储在 inDegrees 和 outDegrees 中。法官这个节点的入度是 n−1, 出度是 0。遍历每个节点的入度和出度。

关键代码：

 vector inDegrees(n+1,0); vector outDegrees(n+1,0); for(auto& edge:trust){ int x=edge[0]; // 信任者 int y=edge[1]; // 被信任者 ++inDegrees[y];  ++outDegrees[x]; } for(int i=1;i<=n;++i){ if (inDegrees[i]==n-1&&outDegrees[i]==0){ return i;  } }

【6】797. 所有可能的路径

日期：8.11

1.题目链接：797. 所有可能的路径 - 力扣（LeetCode）https://leetcode.cn/problems/all-paths-from-source-to-target/description/?envType=problem-list-v2&envId=graph2.题目类型：图，深度优先搜索

3.方法：深度优先搜索（一次题解）

从 0 号点出发，使用栈记录路径上的点。每次遍历到点 n−1，就将栈中记录的路径加入到答案中。特别地，因为本题中的图为有向无环图（DAG），搜索过程中不会反复遍历同一个点，因此无需判断当前点是否遍历过。

关键代码：

 vector<vector> ans; vector stk; // DFS递归函数 void dfs(vector<vector>& graph,int x,int n){ // 终止条件：到达目标节点(n-1) if(x==n){  ans.push_back(stk); return; } // 遍历当前节点的所有邻居 for(auto& y:graph[x]){ stk.push_back(y); dfs(graph, y, n); stk.pop_back(); } } vector<vector> allPathsSourceTarget(vector<vector>& graph){ // 将起始节点0加入路径 stk.push_back(0); // 7. 从节点0开始DFS，目标节点n-1 dfs(graph, 0, graph.size()-1); return ans;

【7】990. 等式方程的可满足性

日期：8.11

1.题目链接：990. 等式方程的可满足性 - 力扣（LeetCode）https://leetcode.cn/problems/satisfiability-of-equality-equations/description/?envType=problem-list-v2&envId=graph2.题目类型：图，并查集

3.方法：并查集（半解）

可以将每一个变量看作图中的一个节点，把相等的关系 == 看作是连接两个节点的边，那么由于表示相等关系的等式方程具有传递性，即如果 a==b 和 b==c 成立，则 a==c 也成立。也就是说，所有相等的变量属于同一个连通分量。因此可以使用并查集来维护这种连通分量的关系。

处理所有等式：将等号连接的变量合并到同一集合

检查所有不等式：如果不等号连接的变量在同一个集合，则矛盾

关键代码：

 bool equationsPossible(vector& equations){ UnionFind uf; // 创建并查集实例 // 处理所有等式 for(const string& str:equations){ if (str[1] == \'=\') {  int index1=str[0]-\'a\';  int index2=str[3]-\'a\';  uf.unite(index1, index2); // 合并两个变量所在的集合 } } // 处理所有不等式 for(const string& str:equations){ if(str[1]==\'!\'){ / int index1=str[0]-\'a\'; int index2=str[3]-\'a\'; // 如果两个变量在同一个集合，则矛盾 if(uf.find(index1)==uf.find(index2)){  return false; } } }

【8】841. 钥匙和房间

日期：8.12

1.题目链接：841. 钥匙和房间 - 力扣（LeetCode）https://leetcode.cn/problems/keys-and-rooms/description/?envType=problem-list-v2&envId=graph2.题目类型：图，深度优先搜索，广度优先搜索

3.方法：深度优先搜索（一次题解）

当 x 号房间中有 y 号房间的钥匙时，可以从 x 号房间去往 y 号房间。如果将这 n 个房间看成有向图中的 n 个节点，那么上述关系就可以看作是图中的 x 号点到 y 号点的一条有向边。这样一来，问题就变成了给定一张有向图，询问从 0 号节点出发是否能够到达所有的节点。

并利用数组 vis 标记当前节点是否访问过，以防止重复访问。

关键代码：

 void dfs(vector<vector>& rooms,int x){ vis[x]=true; num++; for(auto& it:rooms[x]){ if (!vis[it]){ // 递归访问该房间 dfs(rooms, it); } } } bool canVisitAllRooms(vector<vector>& rooms){ int n=rooms.size(); num=0; vis.resize(n);  // 从房间0开始DFS dfs(rooms, 0); return num==n;

4.方法：广度优先搜索（一次题解）

可以使用广度优先搜索的方式遍历整张图，统计可以到达的节点个数，并利用数组 vis 标记当前节点是否访问过，以防止重复访问。

 while(!que.empty()){ int x=que.front();  que.pop(); num++; for(auto& it:rooms[x]){ if(!vis[it]){  vis[it]=true;  que.emplace(it); } } } 

【9】1042. 不邻接植花

日期：8.13

1.题目链接：1042. 不邻接植花 - 力扣（LeetCode）https://leetcode.cn/problems/flower-planting-with-no-adjacent/description/?envType=problem-list-v2&envId=graph2.题目类型：图

3.方法一：颜色标记（半解）

首先建立整个图的邻接列表 adj ；初始化时，将每个花园节点的颜色全部标记为 0；遍历每个花园，并统计其相邻的花园的颜色标记，并从未被标记的颜色中找到一种颜色给当前的花园进行标记；返回所有花园的颜色标记方案即可。

关键代码：

 vector<vector> adj(n); for(auto &path:paths){ // 路径双向连接：花园x-1和y-1 adj[path[0]-1].emplace_back(path[1]-1); adj[path[1]-1].emplace_back(path[0]-1); } vector ans(n, 0); for (int i = 0; i < n; i++) { // 创建颜色标记数组 vector colored(5,false);  // 检查所有邻居已使用的颜色 for(auto &vertex:adj[i]){ // 如果邻居已染色，标记其颜色 if (ans[vertex]!=0){  colored[ans[vertex]]=true; } }// 选择可用的最小数字颜色 for(int j=1;j<=4;j++){ if(colored[j]==false) {  ans[i]=j;  break;} } } return ans;

【10】1791. 找出星型图的中心节点

日期：8.14

1.题目链接：1791. 找出星型图的中心节点 - 力扣（LeetCode）https://leetcode.cn/problems/find-center-of-star-graph/description/?envType=problem-list-v2&envId=graph2.题目类型：图

3.方法一：计算每个节点的度（一次题解）

由 n 个节点组成的星型图中，有一个中心节点，有 n−1 条边分别连接中心节点和其余的每个节点。因此，中心节点的度是 n−1，其余每个节点的度都是 1。一个节点的度的含义是与该节点相连的边数。遍历 edges 中的每条边并计算每个节点的度，度为 n−1 的节点即为中心节点。

 int n=edges.size()+1; vector degrees(n+1); for(auto & edge:edges){ degrees[edge[0]]++; degrees[edge[1]]++; } for(int i=1; ;i++){ if(degrees[i]==n-1){ return i; } }

4.方法二：寻找出现在两条边中的节点（半解）

选择 edges[0] 和 edges[1] 这两条边，则星型图的中心节点是 edges[0][0] 或者 edges[0][1]。如果 edges[0][0] 和 edges[1] 的两个节点之一相同则 edges[0][0] 是星型图的中心节点，如果 edges[0][0] 和 edges[1] 的两个节点都不相同则 edges[0][1] 是星型图的中心节点。

关键代码：

 return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] ? edges[0][0] : edges[0][1];

【11】1976. 到达目的地的方案数

日期：8.14

1.题目链接：1976. 到达目的地的方案数 - 力扣（LeetCode）https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/description/?envType=problem-list-v2&envId=graph2.题目类型：图，最短路

3.方法一：优先队列实现的 Dijkstra 算法（官方题解）

使用Dijkstra算法配合路径计数：

Dijkstra求最短路：计算从起点到各点的最短时间

路径计数：在更新最短路径时记录路径数量

优先队列优化：高效选择当前最短路径节点

动态更新：当找到更短路径时重置计数，当找到等长路径时累加计数

如果从点 u 到点 v 路径，能刷新 dis[v]，则更新 dis[v]，并将 ways[v] 更新为 ways[u]，表示有多少条源到点 u 的最短路径，就有多少条源到点 v 的最短路径。
如果从点 u 到点 v 路径，与 dis[v] 相等。那么 ways[v] 的值要加上 ways[u]，表示点 u 到点 v 路径贡献了另一部分源到点 v 的最短路径。

关键代码：

 // Dijkstra主循环 while(!q.empty()){ auto [t, u]=q.top();  q.pop();  // 如果当前距离大于记录的距离，跳过 if(t>dis[u]){ continue; } // 遍历当前节点的所有邻居 for(auto &[v, w]:e[u]){  LL newTime=t+w; // 新路径时间 // 找到更短路径 if(newTime<dis[v]){  dis[v]=newTime; // 更新最短距离  ways[v]=ways[u]; // 重置路径计数（继承当前节点路径数）  q.emplace(newTime, v); // 加入队列 } // 找到等长路径 else if(newTime==dis[v]){  // 累加路径数量  ways[v]=(ways[u]+ways[v])%mod; } } } return ways[n-1];

【12】1971. 寻找图中是否存在路径

日期：8.15

1.题目链接：1971. 寻找图中是否存在路径 - 力扣（LeetCode）https://leetcode.cn/problems/find-if-path-exists-in-graph/description/?envType=problem-list-v2&envId=graph2.题目类型：图，深度优先搜索，广度优先搜索，并查集

3.方法一：广度优先搜索（半解）

使用广度优先搜索判断顶点 source 到顶点 destination 的连通性，从顶点 source 开始按照层次依次遍历每一层的顶点，检测是否可以到达顶点 destination。遍历过程使用队列存储最近访问过的顶点，同时记录每个顶点的访问状态，每次从队列中取出顶点 vertex 时，将其未访问过的邻接顶点入队列。

关键代码：

 while(!qu.empty()){ int vertex=qu.front(); qu.pop();// 如果当前节点是目标节点，提前终止搜索 if(vertex==destination){ break; // 找到路径，跳出循环 } // 遍历当前节点的所有邻居 for(int next : adj[vertex]){ if(!visited[next]){  qu.emplace(next); visited[next]=true;  } } }

4.方法二：深度优先搜索（一次题解）

深度优先搜索检测顶点 source,destination 的连通性，需要从顶点 source 开始依次遍历每一条可能的路径，判断可以到达顶点 destination，同时还需要记录每个顶点的访问状态防止重复访问。

关键代码：

 if(source==destination){ return true; } //标记当前节点已访问 visited[source]=true; // 遍历当前节点的所有邻居 for(int next:adj[source]){ if(!visited[next]){ if(dfs(next,destination,adj,visited)){  return true; } } } return false;