跳到主要内容

graph

0.说明

  • 此章节代码主要使用cpp
  • 本章题目代码模式倾向于ACM模式

1.基础知识

1.1 图的分类​

  • 有向图
  • 无向图

1.2 度​

  • 无向图中有几条边连接该节点，该节点就有几度
  • 在有向图中，每个节点有出度和入度。
    • 出度：从该节点出发的边的个数。
    • 入度：指向该节点边的个数。 有向图示例
例如对于上面这个图来说，B的入度为1，出度也为1.

1.3 连通性​

  • 对于无向图，若图中任意两点可以到达，即成为连通图。反之，则为非连通图。
    • 在无向图中的极大连通子图称之为该图的一个连通分量
  • 对于有向图，定义与之类似，称之为强连通图和非强连通图。
    • 同理，有向图也存在强连通分量

2.正式开始

2.1 图的构造方法​

  • 邻接表
  • 邻接矩阵

一般来说，图就上面两种构造方法。

ABC
A011
B101
C110

这是一个简易的邻接矩阵示意图。邻接表这种方法适合稠密图。

节点相邻节点
01, 2
13
21
3—

这是一个简单的邻接表示意图。这种方法适合稀疏图。

2.2 处理方式​

2.2.1 DFS​

  • 深度优先（dfs）
    • 类似于树里面的递归遍历
    • 适合找到A->B所有存在的路径这样的题目
#include<iostream>
#include<vector>
using namespace std;
vector<bool> visited;
vector<vector<int>> graph; 
void dfs(int u)
{
  visited[u]=true;
  for(int v:graph[u])
  {
    if(!visited[v])
    {
      dfs(v);
    }
  }
}
//代码此处使用邻接表表示图

2.2.2 BFS​

  • 广度优先（bfs）
    • 类似于树里面的层次遍历
    • 适合找到最短路径这样的题目
    • 一般使用队列来进行，理论上使用栈也是可以的。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(const vector<vector<int>>& graph, int start, int n) 
{
    vector<bool> visited(n, false);  
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        cout << u << " ";  
        for (int v = 0; v < n; ++v) 
        {
            if (graph[u][v] == 1 && !visited[v]) 
            {  
                visited[v] = true;
                q.push(v);
            }
        }
    }
}
//此处使用邻接矩阵表示图

2.2.3 并查集​

  • 并查集

    • 并查集是一种树形数据结构，用于高效地管理不相交集合（Disjoint Sets）的合并（Union）与查询（Find）操作。它支持两种核心操作：

      • Find(x)：查找元素 x 所在集合的代表（通常是根节点），用于判断两个元素是否在同一集合。
      • Union(x, y)：将包含 x 和 y 的两个集合合并为一个集合。

    • 为了提升效率，并查集通常采用两种经典优化：

      • 路径压缩（Path Compression）:在 Find 操作时，将沿途所有节点直接连接到根节点，使下次查询更快。
      • 按秩合并（Union by Rank/Size）:合并时总是将较小的树接到较大的树下，避免树过高，保持操作接近常数时间。 经过这两种优化后，并查集的单次操作平均时间复杂度接近 O(α(n))，其中 α 是反阿克曼函数，增长极慢——对于任何实际规模的 n，α(n) ≤ 5。
struct UnionFind 
{
    vector<int> parent;
    
    UnionFind(int n) 
    {
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i; 
    }
    
    int find(int x) 
    {
        if (parent[x] != x)
            parent[x] = find(parent[x]); 
        return parent[x];
    }
    
    void unite(int x, int y) 
    {
        parent[find(x)] = find(y);
    }
    
    bool same(int x, int y) 
    {
        return find(x) == find(y);
    }
};
//此处为并查集基础模板，可根据实际情况进行调整。

2.2.4 Prim算法​

  • Prim算法是一种用于求解最小生成树（Minimum Spanning Tree, MST）的经典贪心算法，一般适用于带权无向连通图
  • 核心思想是：从一个起始顶点开始，逐步扩展当前已选顶点集合，每次选择一条连接“已选顶点”和“未选顶点”的权重最小的边，直到所有顶点都被包含进来。
  • Prim算法一般是三步走：
    • 第一步，选距离生成树最近节点
    • 第二步，最近节点加入生成树
    • 第三步，更新非生成树节点到生成树的距离

单独讲解比较Prim比较麻烦，想要详细了解可也参考以下文章： prim算法（普里姆算法）详解 最小生成树——Prim算法(详细图解) 代码随想录-prim算法精讲

模板代码参考如下(此处使用邻接矩阵)：

const int INF = INT_MAX;
int prim(const vector<vector<int>>& graph, int n) {
    vector<int> minEdge(n, INF);   // minEdge[i]: 顶点 i 到当前 MST 的最小边权
    vector<bool> inMST(n, false);  // 是否已在 MST 中
    minEdge[0] = 0;                // 从顶点 0 开始
    int totalWeight = 0;

    for (int count = 0; count < n; ++count) {
        // 找到不在 MST 中且 minEdge 最小的顶点 u
        int u = -1;
        for (int v = 0; v < n; ++v) {
            if (!inMST[v] && (u == -1 || minEdge[v] < minEdge[u]))
                u = v;
        }

        if (minEdge[u] == INF) {
            // 图不连通
            return -1;
        }

        inMST[u] = true;
        totalWeight += minEdge[u];

        // 更新 u 的邻居
        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != 0 && !inMST[v]) {
                if (graph[u][v] < minEdge[v]) {
                    minEdge[v] = graph[u][v];
                }
            }
        }
    }

    return totalWeight;
}

2.2.5 Kruskal算法​

  • 与Prim算法类似，都是用于求解最小生成树（Minimum Spanning Tree, MST）的经典贪心算法。它们的目标是在一个带权无向连通图中，找到一棵包含所有顶点、边权总和最小的生成树。
  • 与Prim算法不同，Kruskal算法以边为主导（Prim算法以顶点为主导），按边的权重从小到大依次考虑每条边，如果加入该边不会形成环（即连接的是两个不同的连通分量），就将其加入生成树中。
  • 一般情况下，这两种算法可以互换使用。在实际使用中，一般来说，图较为稀疏（即边数远小于v2）时使用Kruskal算法，反之使用Prim算法。

详细了解的话可以参考以下文章： 代码随想录-Kruskal算法 kruskal算法透彻理解 kruskal算法（克鲁斯卡尔算法）详解

Kruskal算法步骤：

  • 任选一个起始顶点，将其加入 MST。
  • 维护一个优先队列（或最小堆），存储所有连接 MST 与非 MST 顶点的边。
  • 每次从队列中取出权重最小的边，若其另一端点不在 MST 中，则加入该顶点和边。
  • 重复直到 MST 包含所有顶点。

一般来说，Kruskal会判断一条边的两点是否已经联通（防止出现环），故而常用并查集来检查两点的父节点关系。后续Kruskal中的并查集代码可参考并查集中的模板代码。

模板代码参考如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 并查集（Disjoint Set Union, DSU）结构
struct DSU {
    vector<int> parent;   // parent[i] 表示节点 i 的父节点
    vector<int> rank;     // rank[i] 用于按秩合并优化

    // 构造函数：初始化并查集，每个节点初始时独立成一个集合
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i)
            parent[i] = i;  // 自己是自己的根
    }

    // 查找 x 所在集合的根（带路径压缩）
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // 路径压缩：直接连到根
        return parent[x];
    }

    // 合并 x 和 y 所在的集合（按秩合并）
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;  // 已在同一集合，无需合并

        // 按秩合并：将小树接到大树下
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[y] = x;
            rank[x]++;
        }
        return true;  // 成功合并
    }
};

// 边的结构体
struct Edge {
    int u, v, weight;
    // 构造函数（可选）
    Edge(int _u, int _v, int _w) : u(_u), v(_v), weight(_w) {}
    
    // 重载 < 运算符，用于按权重升序排序
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

// Kruskal 算法主函数
// 参数：n 为顶点数（顶点编号从 0 到 n-1），edges 为所有边的列表
// 返回：最小生成树的总权重；若图不连通，则返回 -1（或根据需求调整）
long long kruskal(int n, vector<Edge>& edges) {
    // 按边权从小到大排序
    sort(edges.begin(), edges.end());

    DSU dsu(n);                // 初始化并查集
    long long mst_weight = 0;  // MST 的总权重
    int edges_used = 0;        // 已加入 MST 的边数

    // 遍历所有边
    for (const Edge& e : edges) {
        // 如果 u 和 v 不在同一连通分量，则加入 MST
        if (dsu.unite(e.u, e.v)) {
            mst_weight += e.weight;
            edges_used++;
            // 若已选 n-1 条边，MST 构建完成
            if (edges_used == n - 1) break;
        }
    }

    // 判断是否形成生成树（即图是否连通）
    if (edges_used != n - 1) {
        return -1;  // 图不连通，无法构建 MST
    }

    return mst_weight;
}

// 示例用法
int main() {
    int n = 4;  // 顶点数
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    long long result = kruskal(n, edges);
    if (result == -1) {
        cout << "图不连通，无法生成最小生成树。\n";
    } else {
        cout << "最小生成树的总权重为: " << result << "\n";
    }

    return 0;
}

2.2.6 Dijkstra算法​

  • 与上面的Prim算法和Kruskal算法一样，Dijkstra算法也是一种使用贪心策略的算法。
  • 与前两者不同的是，Dijkstra算法用来解决两点间最短路径之类的问题，因此该算法关注的侧重点为总路径长度（即权重和）而不是像Prim、Kruskal一样关注单独的边的长度。
  • 基于Dijkstra的特性，该算法适合解决类似于导航、任务调度、路由算法之类的问题。

核心思想：

  • 维护一个集合 S ，表示已经确定最短路径的顶点；
  • 对于每个不在 S 中的顶点 v ，维护一个当前已知的从源点 s 到 v 的最短距离估计值 d[v] ；
  • 每次从未确定最短路径的顶点中选择 d[v] 最小的那个，将其加入 S ，并用它来松弛（relax）其邻接点的距离。

参考的模板代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int INF = INT_MAX;

// 图用邻接表表示：graph[u] = vector of {v, weight}
using Graph = vector<vector<pair<int, int>>>;

vector<int> dijkstra(const Graph& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        // 如果当前距离已经比记录的大，说明是旧值，跳过
        if (d != dist[u]) continue;
        
        for (auto &edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

2.2.7 Bellman_ford算法​

与上面的Dijkstra不同，Bellman-Ford 算法可以处理带负权边的图（但不能有从源点可达的负权环）

实例代码如下：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 定义一条边的结构体：起点 u，终点 v，权重 weight
struct Edge {
    int u, v, weight;
};

// Bellman-Ford 算法主函数
// 参数：
//   n: 顶点数量（顶点编号从 0 到 n-1）
//   edges: 所有边的列表
//   src: 源点（起点）
// 返回值：
//   true 表示没有负权环，false 表示存在从 src 可达的负权环
bool bellmanFord(int n, const vector<Edge>& edges, int src) {
    // 初始化距离数组：dist[i] 表示从 src 到 i 的最短距离
    vector<long long> dist(n, LLONG_MAX); // 使用 long long 防止溢出
    dist[src] = 0; // 源点到自己的距离为 0

    // 松弛操作：进行 n - 1 轮
    // 因为任意最短路径最多包含 n - 1 条边
    for (int i = 0; i < n - 1; ++i) {
        bool updated = false; // 用于提前终止优化（可选）

        // 遍历所有边，尝试松弛
        for (const auto& e : edges) {
            // 如果起点 u 的距离尚未确定（仍是无穷大），跳过
            if (dist[e.u] == LLONG_MAX) continue;

            // 如果通过 u -> v 能获得更短路径，则更新 dist[v]
            if (dist[e.u] + e.weight < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.weight;
                updated = true;
            }
        }

        // 如果本轮没有更新任何距离，说明已经收敛，可以提前退出
        if (!updated) break;
    }

    // 第 n 轮：检查是否存在负权环
    bool hasNegativeCycle = false;
    for (const auto& e : edges) {
        if (dist[e.u] == LLONG_MAX) continue;

        // 如果还能继续松弛，说明存在负权环
        if (dist[e.u] + e.weight < dist[e.v]) {
            hasNegativeCycle = true;
            break;
        }
    }

    // 输出结果
    if (hasNegativeCycle) {
        cout << "图中存在从源点可达的负权环！\n";
        return false;
    } else {
        cout << "从源点 " << src << " 到各点的最短距离为：\n";
        for (int i = 0; i < n; ++i) {
            if (dist[i] == LLONG_MAX) {
                cout << "到顶点 " << i << "：不可达\n";
            } else {
                cout << "到顶点 " << i << "："<< dist[i] << "\n";
            }
        }
        return true;
    }
}

这个是完整的，遇到实际问题时根据问题具体求的是什么来对这个代码进行修改。

3.题目练习中学习

3.1 BFS和DFS相关​

3.1.1 所有可达路径​

link:所有可达路径

//解答代码如下：
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> result;
vector<int> path;
void dfs(int node, int N, const vector<vector<int>> &graph, vector<bool> &visited) {
  if (node == N) {
    result.push_back(path);
    return;
  }

  for (int neighbor : graph[node]) {
    if (!visited[neighbor]) {
      visited[neighbor] = true;
      path.push_back(neighbor);
      dfs(neighbor, N, graph, visited);
      path.pop_back();
      visited[neighbor] = false;
    }
  }
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> graph(N + 1);
  while (M--) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
  }
  vector<bool> visited(N + 1, false);
  path.push_back(1);
  dfs(1, N, graph, visited);
  if (result.size() == 0)
    cout << -1 << endl;
  for (const vector<int> &pa : result) {
    for (int i = 0; i < pa.size() - 1; i++) {
      cout << pa[i] << " ";
      }
    cout << pa[pa.size() - 1] << endl;
    }
    return 0;
  }

这是一道很简单的模板题，算是记住dfs模板的一道标准题目了。 本题就是上文说的那种找到所有路径的题目。 故而与2.2 处理方法中的dfs模板类似，直接使用就行，难度不算高。

3.1.2 计数孤岛​

link：计数孤岛

//解答代码如下：
#include<iostream>
#include<vector>
using namespace std;

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

void dfs(const vector<vector<int>>& graph,vector<vector<bool>>& visited,int u,int v)
{
    for(int i=0;i<4;i++)
    {
        int du=u+dx[i];
        int dv=v+dy[i];
        if(du<graph.size()&&du>=0&&dv<graph[0].size()&&dv>=0)
        {
            if(graph[du][dv]==1&&!visited[du][dv])
            {
                visited[du][dv]=true;
                dfs(graph,visited,du,dv);
            }
        }
    }
}

int main()
{
    int N,M;
    cin>>N>>M;
    vector<vector<int>> graph(N,vector<int> (M));
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            cin>>graph[i][j];
        }
    }
    vector<vector<bool>> visited(N,vector<bool> (M,false));
    int count=0;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            if(!visited[i][j]&&graph[i][j]==1)
            {
                count++;
                dfs(graph,visited,i,j);
            }
        }
    }
    cout<<count<<endl;
    return 0;
}

本题依旧是一个模板题，用来熟悉模板的。 理论上这个题用bfs也能做，但是考虑到bfs条件没判断好的话很容易超时，此处依旧使用dfs来处理。

3.1.3 最大岛屿面积​

link：最大岛屿面积

//解答代码如下（dfs版）：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int max_s=0;


int dfs(const vector<vector<int>>& grid,vector<vector<bool>>& visited,int u,int v)
{
    int s=1;
    visited[u][v]=true;
    for(int i=0;i<4;i++)
    {
        int du=u+dx[i];
        int dv=v+dy[i];
        if (du >= 0 && du < grid.size() && dv >= 0 && dv < grid[0].size()) 
        {
            if (grid[du][dv] == 1 && !visited[du][dv]) 
            {
                s += dfs(grid, visited, du, dv); 
            }
        }
    }
    return s;
}

int main()
{
    int N,M;
    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];
        }
    }
    int s=0;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            if(grid[i][j]==1&&!visited[i][j])
            {
                s+=dfs(grid,visited,i,j);
                max_s=max(max_s,s);
                s=0;
            }
        }

    }
    cout<<max_s<<endl;
    return 0;
}
//解答代码如下（bfs版）：
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

// BFS 函数：从 (start_x, start_y) 开始搜索，返回连通区域的面积
int bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int start_x, int start_y) {
    int N = grid.size();
    int M = grid[0].size();
    queue<pair<int, int>> q;
    q.push({start_x, start_y});
    visited[start_x][start_y] = true;
    int area = 0;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        area++;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M &&
                grid[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }

    return area;
}

int main() {
    int N, M;
    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];
        }
    }

    int max_area = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                int area = bfs(grid, visited, i, j);
                max_area = max(max_area, area);
            }
        }
    }

    cout << max_area << endl;
    return 0;
}

依旧是个模板题，拿来巩固bfs和dfs模板的。

3.1.4 沉没孤岛​

link:沉没孤岛

//解答代码如下：
#include<iostream>
#include<vector>
using namespace std;

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int u, int v)
{
    visited[u][v] = true;
    for (int i = 0; i < 4; i++)
    {
        int du = u + dx[i];
        int dv = v + dy[i];
        if (du >= 0 && du < grid.size() && dv >= 0 && dv < grid[0].size())
        {
            if (grid[du][dv] == 1 && !visited[du][dv])
            {
                dfs(grid, visited, du, dv);
            }
        }
    }
}

int main()
{
    int N, M;
    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];
        }
    }
    for (int i = 0; i < N; i++)
    {
        if (grid[i][0] == 1)
        {
            dfs(grid, visited, i, 0);
        }
        if (grid[i][M - 1] == 1)
        {
            dfs(grid, visited, i, M - 1);
        }
    }
    for (int j = 0; j < M; j++)
    {
        if (grid[0][j] == 1)
        {
            dfs(grid, visited, 0, j);
        }
        if (grid[N - 1][j] == 1)
        {
            dfs(grid, visited, N - 1, j);
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (grid[i][j] == 1 && !visited[i][j])
            {
                grid[i][j] = 0;
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

这个题比上面的会稍微麻烦一些，此处我们采用类似于'灌水法'的方法。 灌水法（反向思维）： 从边界出发，把所有能从边界到达的 1 标记为“可逃逸”； 剩下的未被标记的 1，就是被完全包围的、无法到达边界的，即“封闭岛屿”或“飞地”； 然后根据题目要求，保留 or 删除这些封闭区域。 这就像从海洋（边界）往陆地“灌水”，能被水淹没的陆地（与边界连通的 1）保留，没被淹到的就是内陆湖/孤岛，按需处理。

3.1.5 高山流水​

link:高山流水

#include <iostream>
#include <vector>
using namespace std;

// 四个方向：下、上、右、左
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// DFS：从 (u, v) 开始，沿着高度不下降的方向（即水能流到的地方）进行遍历
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int u, int v) {
    int n = grid.size();
    int m = grid[0].size();

    for (int i = 0; i < 4; i++) {
        int du = u + dx[i];
        int dv = v + dy[i];

        // 检查是否越界
        if (du < 0 || du >= n || dv < 0 || dv >= m) continue;

        // 如果已经访问过，跳过
        if (visited[du][dv]) continue;

        // 水只能从高往低或平地流：所以相邻格子高度必须 >= 当前格子（反向思考：从边界往里走，要求不下降）
        if (grid[du][dv] >= grid[u][v]) {
            visited[du][dv] = true;
            dfs(grid, visited, du, dv);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<bool>> on_visited(n, vector<bool>(m, false));      // 能从上/左边界流到的点
    vector<vector<bool>> down_visited(n, vector<bool>(m, false));   // 能流到下/右边界的点

    // 输入网格
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    // 从上边界（i=0）和左边界（j=0）开始 DFS，标记 on_visited
    for (int i = 0; i < n; i++) {
        on_visited[i][0] = true;
        dfs(grid, on_visited, i, 0);
    }
    for (int j = 0; j < m; j++) {
        on_visited[0][j] = true;
        dfs(grid, on_visited, 0, j);
    }

    // 从下边界（i=n-1）和右边界（j=m-1）开始 DFS，标记 down_visited
    for (int i = 0; i < n; i++) {
        down_visited[i][m - 1] = true;
        dfs(grid, down_visited, i, m - 1);
    }
    for (int j = 0; j < m; j++) {
        down_visited[n - 1][j] = true;
        dfs(grid, down_visited, n - 1, j);
    }

    // 找出两个 visited 都为 true 的位置，即“高山流水”可达的点
    vector<pair<int, int>> result;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (on_visited[i][j] && down_visited[i][j]) {
                result.push_back({i, j});
            }
        }
    }

    // 输出结果（按行列顺序）
    for (auto& p : result) {
        cout << p.first << " " << p.second << endl;
    }

    return 0;
}

此题采用反向 DFS，即与上题类似的灌水法。 从上/左边界出发，沿高度不下降方向遍历，标记能到达的点（on_visited）； 从下/右边界出发，同样沿高度不下降方向遍历，标记能到达的点（down_visited）； 两个标记都为 true 的位置即为答案。 核心思想：水往低处流 → 反向搜索时只能走向 ≥ 当前高度的格子。

3.1.6 建造最大岛屿​

link：建造最大岛屿

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

// DFS 函数：给岛屿编号并返回面积
int dfs(vector<vector<int>>& grid, int x, int y, int islandId) {
    int n = grid.size(), m = grid[0].size();
    if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 1) {
        return 0;
    }
    grid[x][y] = islandId; // 标记为当前岛屿 ID
    int area = 1;
    // 四个方向
    area += dfs(grid, x + 1, y, islandId);
    area += dfs(grid, x - 1, y, islandId);
    area += dfs(grid, x, y + 1, islandId);
    area += dfs(grid, x, y - 1, islandId);
    return area;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    int totalOnes = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
            totalOnes += grid[i][j];
        }
    }

    // 特判：全为 1
    if (totalOnes == n * m) {
        cout << n * m << '\n';
        return 0;
    }

    // 第一步：遍历所有 1，进行 DFS 编号，并记录每个岛屿的面积
    unordered_map<int, int> areaMap; // islandId -> area
    int islandId = 2; // 从 2 开始编号（0 和 1 已被使用）

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1) {
                int area = dfs(grid, i, j, islandId);
                areaMap[islandId] = area;
                ++islandId;
            }
        }
    }

    // 第二步：枚举每个 0，尝试填海
    int maxArea = 0;
    // 至少存在一个岛屿时，maxArea 至少是最大原始岛屿面积
    if (!areaMap.empty()) {
        maxArea = (*max_element(areaMap.begin(), areaMap.end(),
            [](const auto& a, const auto& b) { return a.second < b.second; })).second;
    }

    vector<pair<int, int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 0) {
                unordered_set<int> neighborIds; // 防止重复加同一个岛屿
                for (auto& [dx, dy] : dirs) {
                    int ni = i + dx, nj = j + dy;
                    if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] > 1) {
                        neighborIds.insert(grid[ni][nj]);
                    }
                }
                int total = 1; // 当前格子变为陆地
                for (int id : neighborIds) {
                    total += areaMap[id];
                }
                maxArea = max(maxArea, total);
            }
        }
    }

    cout << maxArea << '\n';
    return 0;
}

这个题比前面的要难不少，如果直接把每个0改成1进行dfs的话，时间复杂度会达到O(n4)，显然会超时。此时采用 两阶段策略： 第一阶段：预处理所有原始岛屿。对每个未访问的 1 做 DFS，给它分配一个唯一的 岛屿编号（从 2 开始）。同时记录每个编号对应的 岛屿面积（存入 areaMap）。这样，整个网格中的 1 都被替换成其所属岛屿的 ID（≥2），方便后续快速识别。 第二阶段：枚举每个 0，模拟填海。对每个 0，查看其上下左右四个邻居： 如果邻居是某个岛屿（即值 ≥2），就记录该岛屿的 ID。 使用 unordered_set 去重（避免同一个岛屿被加多次）。 总面积 = 1（新填的格子） + 所有相邻不同岛屿的面积之和。 更新全局最大面积 maxArea。 边界情况处理 如果整个网格全是 1（没有 0），直接返回 n * m。 如果没有岛屿（全是 0），那填一个格子后最大面积就是 1（但题目通常保证至少有一个 1，不过代码通过 areaMap.empty() 也做了安全处理）。

3.1.7 有向图的完全联通​

link:有向图的完全联通 做了不少无向图的，此处做一个有向图的题目。

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

void bfs(const vector<vector<int>>& graph, vector<bool>& visited, int start) 
{
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) 
    {
        int u = q.front(); 
        q.pop();
        for (int v : graph[u]) 
        {
            if (!visited[v]) 
            {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int op(vector<bool>& visited)
{
    for(int i=0;i<visited.size();i++)
    {
        if(!visited[i])
        {
            return -1;
        }
    }
    return 1;
}

int main()
{
    int n,k;
    cin>>n>>k;
    vector<vector<int>> graph(n);
    for(int i=0;i<k;i++)
    {
        int a,b;
        cin>>a>>b;
        graph[a-1].push_back(b-1);
    }
    vector<bool> visited(n,false);
    visited[0]=true;
    bfs(graph,visited,0);
    cout<<op(visited)<<endl;
}

题目不算难，此处使用bfs来进行处理。 此题只是为了熟悉有向图，不做其他解读。

3.2 并查集相关​

3.2.1 建造最大岛屿​

link：建造最大岛屿 此题与上面建造最大岛屿是同一题目，此处可以使用并查集来进行处理，，将上面代码中格子的编号抽象为其父节点，参考代码如下：

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<algorithm>

using namespace std;

class DSU {
public:
    map<pair<int, int>, pair<int, int>> p;  

    pair<int, int> find(pair<int, int> x) 
    {
        if (!p.count(x)) 
        {
            p[x] = x;
        }
        if (p[x] != x) 
        {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    void unite(pair<int, int> x, pair<int, int> y) 
    {
        auto rx = find(x), ry = find(y);
        if (rx != ry) 
        {
            p[rx] = ry;
        }
    }
};

int main() 
{
    int n, m;
    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];
        }
    }

    DSU dsu;
    // 初始化并查集，把所有的陆地加入并查集
    // 我们用 pair(i,j) 表示坐标
    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < m; ++j) 
        {
            if (grid[i][j] == 1) 
            {
                dsu.p[{i, j}] = {i, j};  // 初始化父节点
            }
        }
    }

    // 建立连接：将相邻的陆地合并
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < m; ++j) 
        {
            if (grid[i][j] == 1) 
            {
                for (int d = 0; d < 4; ++d) 
                {
                    int ni = i + dx[d], nj = j + dy[d];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == 1) 
                    {
                        dsu.unite({i, j}, {ni, nj});
                    }
                }
            }
        }
    }

    // 统计每个根节点对应的岛屿大小
    map<pair<int, int>, int> size;
    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < m; ++j) 
        {
            if (grid[i][j] == 1) 
            {
                auto root = dsu.find({i, j});
                size[root]++;
            }
        }
    }

    int maxArea = 0;

    // 枚举每一个水格子 (0)，尝试填成陆地
    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < m; ++j) 
        {
            if (grid[i][j] == 0) 
            {
                set<pair<int, int>> neighbors;  // 存储周围的岛屿根节点，避免重复
                for (int d = 0; d < 4; ++d) 
                {
                    int ni = i + dx[d], nj = j + dy[d];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == 1) 
                    {
                        auto root = dsu.find({ni, nj});
                        neighbors.insert(root);
                    }
                }

                // 计算合并后的面积
                int newArea = 1;  // 新增的陆地
                for (auto& root : neighbors) 
                {
                    newArea += size[root];
                }

                maxArea = max(maxArea, newArea);
            }
        }
    }

    // 如果原来就有最大岛屿，也要考虑
    for (auto& [root, s] : size) 
    {
        maxArea = max(maxArea, s);
    }

    cout << maxArea << endl;

    return 0;
}

3.2.2 寻找存在的路线​

link:寻找存在的路线 参考代码如下：

#include<iostream>
#include<vector>

using namespace std;

struct UnionFind 
{
    vector<int> parent;
    
    UnionFind(int n) 
    {
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i; 
    }
    
    int find(int x) 
    {
        if (parent[x] != x)
            parent[x] = find(parent[x]); 
        return parent[x];
    }
    
    void unite(int x, int y) 
    {
        parent[find(x)] = find(y);
    }
    
    bool same(int x, int y) 
    {
        return find(x) == find(y);
    }
};
//此处UnionFind即常见并查集模板

int main()
{
    int n,m;
    cin>>n>>m;
    UnionFind uf(n);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        uf.unite(a-1,b-1);
    }
    int s,d;
    cin>>s>>d;
    if(uf.same(s-1,d-1))
    {
        cout<<1<<endl;
    }
    else
    {
        cout<<0<<endl;
    }
    return 0;
}

这是一个基础的并查集模板题，此处拿来复习一下并查集模板。

3.2.3 多余的边​

link:多余的边 解答代码如下：

#include<iostream>
#include<vector>

using namespace std;

struct UnionFind
{
    vector<int> parent;

    UnionFind(int n) 
    {
        parent.resize(n);
        for (int i = 0; i < n; i++) 
        {
            parent[i] = i;
        }
    }

    int find(int x)
    {
        if(parent[x]!=x)
        {
            parent[x]=find(parent[x]);
        }
        return parent[x];
    }

    void unite(int x, int y) 
    {
        parent[find(x)] = find(y); 
    }
    
    bool same(int x, int y) 
    {
        return find(x) == find(y);
    }
};

int main()
{
    int n;
    cin>>n;
    UnionFind uf(n);
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        if(uf.same(a-1,b-1))
        {
            cout<<a<<" "<<b<<endl;
            break;
        }
        else
        {
            uf.unite(a-1,b-1);
        }
    }
    return 0;
}

这个题目比较特殊，因为题目中规定了n个节点、n-1条边，且只多一条冗余的边。题目要求输出最先出现的冗余的边，故而使用并查集模板之后看那两个点最先出现父节点相同即可。 与之类似的可以查看变种题多余的边II

3.3 Prim算法相关​

3.3.1 寻宝​

link:寻宝 参考代码如下：

#include<iostream>
#include<vector>
#include<climits>

using namespace std;
const int INF = INT_MAX;

int prim(const vector<vector<int>>& graph, int n) {
    vector<int> minEdge(n, INF);   // minEdge[i]: 顶点 i 到当前 MST 的最小边权
    vector<bool> inMST(n, false);  // 是否已在 MST 中
    minEdge[0] = 0;                // 从顶点 0 开始
    int totalWeight = 0;

    for (int count = 0; count < n; ++count) 
    {
        // 找到不在 MST 中且 minEdge 最小的顶点 u
        int u = -1;
        for (int v = 0; v < n; ++v) 
        {
            if (!inMST[v] && (u == -1 || minEdge[v] < minEdge[u]))
               {
                 u = v;
               }
        }

        if (minEdge[u] == INF) 
        {
            // 图不连通
            return -1;
        }

        inMST[u] = true;
        totalWeight += minEdge[u];

        // 更新 u 的邻居
        for (int v = 0; v < n; ++v) 
        {
            if (graph[u][v] != 0 && !inMST[v]) 
            {
                if (graph[u][v] < minEdge[v]) 
                {
                    minEdge[v] = graph[u][v];
                }
            }
        }
    }

    return totalWeight;
}
//此处为prim算法简单模板代码

int main()
{
    int v,e;
    cin>>v>>e;
    vector<vector<int>> graph(v,vector<int>(v,0));
    for(int i=0;i<e;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        graph[a-1][b-1]=c;
        graph[b-1][a-1]=c;
    }
    cout<<prim(graph,v)<<endl;
}

此题是一个最好的使用prim算法的题目，prim最适合解决连接所有节点、总边权最小的问题，与此题中两点间铺路完全相符，故而使用此题来巩固prim的模板代码。

3.3.2 连接所有点的最小费用​

link:连接所有点的最小费用 解答代码如下：

class Solution 
{
public:

    const int INF=INT_MAX;

    int le(int x1,int y1,int x2,int y2)
    {
        return abs(x1-x2)+abs(y1-y2);
    }

    int prim(vector<vector<int>>& grid,int n)
    {
        vector<int> minEdge(n,INF);
        vector<bool> inMST(n,false);
        minEdge[0]=0;
        int totallength=0;

        for(int i=0;i<n;i++)
        {
            int u=-1;
            for(int v=0;v<n;v++)
            {
                if(!inMST[v]&&(u==-1||minEdge[v]<minEdge[u]))
                {
                    u=v;
                }
            }
            if(minEdge[u]==INF)
            {
                return -1;
            }
            inMST[u]=true;
            totallength+=minEdge[u];
            for(int v=0;v<n;v++)
            {
                if(grid[u][v]!=0&&!inMST[v])
                {
                    minEdge[v]=min(minEdge[v],grid[u][v]);
                }
            }
        }
        return totallength;
    }

    int minCostConnectPoints(vector<vector<int>>& points) 
    {
        int n=points.size();
        vector<vector<int>> grid(n,vector<int>(n,0));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                grid[i][j]=le(points[i][0],points[i][1],points[j][0],points[j][1]);
                grid[j][i]=le(points[i][0],points[i][1],points[j][0],points[j][1]);
            }
        }
        return prim(grid,n);
    }
};

这个题目是leetcode上的一个模板题目，理论上可以使用prim和kruskal两种算法都可以做出来，此处使用prim来处理，依旧是将prim的模板代码套上去，然后使用le函数计算两点间的距离，最后在主函数中return prim()即可。

3.4 Kruskal算法相关​

3.4.1 寻宝​

此题与3.3.1 寻宝为同一题目，此处使用Kruskal算法来处理，同时巩固Kruskal算法模板。 代码如下：

#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

struct Edge
{
    int v1,v2,val;
};

struct UnionFind
{
    vector<int> parents;
    UnionFind(int n)
    {
        parents.resize(n);
        for(int i=0;i<n;i++)
        {
            parents[i]=i;
        }
    }
    int find(int x)
    {
        if(parents[x]!=x)
        {
            parents[x]=find(parents[x]);
        }
        return parents[x];
    }
    void unite(int x,int y)
    {
        parents[find(y)]=find(x);
    }
    bool same(int x,int y)
    {
        return find(x)==find(y);
    }
};

long long kruskal(int n,vector<Edge>& edge)
{
    sort(edge.begin(),edge.end(),[](const Edge& a,const Edge& b) {return a.val<b.val;});
    UnionFind uf(n);
    long long totallength=0;
    int used_edge=0;
    for(const auto& e:edge)
    {
        if(!uf.same(e.v1,e.v2))
        {
            uf.unite(e.v1,e.v2);
            totallength+=e.val;
            used_edge++;
        }
        if(used_edge==n-1)
        {
            break;
        }
    }
    return totallength;
}

int main()
{
    int v,e;
    cin>>v>>e;
    vector<Edge> edge(e);
    for(int i=0;i<e;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i].v1=a-1;
        edge[i].v2=b-1;
        edge[i].val=c;
    }
    cout<<kruskal(v,edge)<<endl;
    return 0;
}

3.4.2 最小生成树​

link:最小生成树 解答代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge
{
  int x,y,z;  
};
struct UnionFind
{
    vector<int> parents;
    UnionFind(int n)
    {
        parents.resize(n);
        for(int i=0;i<n;i++)
        {
            parents[i]=i;
        }
    }
    int find(int x)
    {
        if(parents[x]!=x)
        {
            parents[x]=find(parents[x]);
        }
        return parents[x];
    }
    void unite(int x,int y)
    {
        parents[find(y)]=find(x);
    }
    bool same(int x,int y)
    {
        return find(x)==find(y);
    }
};
long long kruskal(vector<Edge>& edge,int n)
{
    sort(edge.begin(),edge.end(),[](const Edge& a,const Edge& b){return a.z<b.z;});
    UnionFind uf(n);
    long long totallength=0;
    int used_edge=0;
    for(auto& i:edge)
    {
        if(!uf.same(i.x,i.y))
        {
            uf.unite(i.x,i.y);
            used_edge++;
            totallength+=i.z;
            if(used_edge==n-1)
            {
                break;
            }
        }
    }
    if(used_edge!=n-1)
    {
        return -1;
    }
    return totallength;
}
int main()
{
    int n,m;
    cin>>n>>m;
    vector<Edge> edge(m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i].x=a-1;
        edge[i].y=b-1;
        edge[i].z=c;
    }
    long long ans=kruskal(edge,n);
    if(ans==-1)
    {
        cout<<"orz";
    }
    else
    {
        cout<<ans;
    }
    return 0;
}

这个题比上面的题目多了一步，因为这个题目存在非连通图，因此我们要加上一个if(used_edge!=n-1)的判断来处理非联通图，其他的和模板一样来写就可以了。

3.5 Dijkstra算法相关​

3.5.1 参加科学大会​

link:参加科学大会

#include<iostream>
#include<vector>
#include<queue>
#include<climits>

using namespace std;

vector<int> Dijkstra(int n,int start,const vector<vector<pair<int, int>>>& graph)
{
    vector<int> dist(n,INT_MAX);
    dist[start]=0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0,start});
    while (!pq.empty()) 
    {
        auto [cur_dist, u] = pq.top();
        pq.pop();

        // 剪枝：跳过已处理过的节点
        if (cur_dist > dist[u]) continue;

        // 遍历邻边（pair的first是to，second是weight）
        for (const auto& edge : graph[u]) 
        {
            int v = edge.first;    // 目标节点
            int w = edge.second;   // 边的权重

            // 松弛操作
            if (dist[v] > dist[u] + w) 
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>>> graph(n);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        graph[a-1].insert(graph[a-1].end(),{b-1,c});
    }
    vector<int> ans=Dijkstra(n,0,graph);
    if(ans[n-1]==INT_MAX)
    {
        cout<<-1;
    }
    else
    {
        cout<<ans[n-1];
    }
    return 0;
}

这个题也是一个模板题，用来巩固Dijkstra算法模板的，此处的算法模板使用的是类似于bfs的处理方法。

3.5.2 单源最短路径​

link:单源最短路径 解答代码如下：

#include<iostream>
#include<vector>
#include<queue>
#include<climits>
#include<algorithm>
using namespace std;
vector<int> Dijkstra(int n,int start,const vector<vector<pair<int, int>>>& graph)
{
    vector<int> dist(n,INT_MAX);
    dist[start]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    pq.push({0,start});
    while(!pq.empty())
    {
        auto [cur_dist,u]=pq.top();
        pq.pop();
        if (cur_dist > dist[u]) continue;
        for(const auto& edge : graph[u] )
        {
            int v=edge.first;
            int w=edge.second;
            if(dist[v]>dist[u]+w)
            {
                dist[v]=dist[u]+w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
int main()
{
    int n,m,s;
    cin>>n>>m>>s;
    vector<vector<pair<int,int>>> graph(n);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        graph[a-1].emplace_back(b-1,c);
    }
    vector<int> dist=Dijkstra(n,s-1,graph);
    for(int i=0;i<dist.size();i++)
    {
        if(i<dist.size()-1)
        {
            cout<<dist[i]<<" ";
        }
        else
        {
            cout<<dist[i];
        }
    }
    return 0;
}

和上面题一样，这也是一个模板题，把模板弄对基本上就过了。

3.6 Bellman_ford算法与负权图相关​

3.6.1 城市间货物运输 I​

link:城市间货物运输 I 参考代码如下：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
struct Edge
{
    int u,v,w;
};
const long long INF = LLONG_MAX;
long long BellmanFord(int n, const vector<Edge>& edges, int s, int t) {
    vector<long long> dist(n, INF);
    dist[s] = 0;

    // 松弛 n-1 次
    for (int i = 0; i < n - 1; ++i) {
        bool updated = false;
        for (const auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                updated = true;
            }
        }
        if (!updated) break;
    }

    // 检查是否存在从 s 可达、且能到达 t 的负权环
    vector<long long> dist2 = dist; // 再松弛一次
    for (const auto& e : edges) {
        if (dist2[e.u] != INF && dist2[e.u] + e.w < dist2[e.v]) {
            dist2[e.v] = -INF; // 标记可能受负环影响的点
        }
    }

    // 传播负环影响（可选，更严谨的做法是 BFS/DFS 标记所有被负环影响的点）
    // 简化处理：再做 n 次松弛，把所有能被负环“更新”的点设为 -INF
    for (int i = 0; i < n; ++i) {
        for (const auto& e : edges) {
            if (dist2[e.u] == -INF) {
                dist2[e.v] = -INF;
            }
        }
    }

    if (dist2[t] == -INF) {
        // 说明 t 受到负权环影响，最短路径无下界
        return -INF;
    }
    return dist[t];
}
int main()
{
    int n,m;
    cin>>n>>m;
    vector<Edge> edges(m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edges[i]={a-1,b-1,c};
    }
    long long ans=BellmanFord(n,edges,0,n-1);
    if(ans==INF)
    {
        cout<<"unconnected";
    }
    else
    {
        cout<<ans;
    }
    return 0;
}

这个题目是一个经典的带有负权图的题目，因此我们不能使用Dijkstra算法，而应使用Bellman Ford算法。此处使用的模板是上面Bellman_ford算法模板的改动版。因为题目并未要求判断这个图是否是负权图，故而把bool判断那一块删除修改了。

4.图论巩固（此处题目以中难题为主）

4.1 单词接龙​

link:单词接龙 参考代码如下：

class Solution 
{
public:
    vector<vector<int>> mp; // 邻接矩阵
    unordered_map<string, vector<int>> up; // 通配符模式 -> 单词索引列表

    // 建图函数：将单词 s（索引为 m）的所有通配符模式加入 up，并记录索引
    void buildGraph(const string& s, int m)
    {
        int len = s.size();
        for (int i = 0; i < len; i++)
        {
            string temp = s;
            temp[i] = '*'; // 用 '*' 作为通配符
            up[temp].push_back(m);
        }
    }

    // 根据 up 构建邻接矩阵
    void buildAdjMatrix(int totalWords)
    {
        mp.assign(totalWords, vector<int>(totalWords, 0));
        
        // 遍历所有通配符模式
        for (auto& [pattern, indices] : up)
        {
            // 同一个模式下的所有单词两两相连
            for (int i = 0; i < indices.size(); i++)
            {
                for (int j = i + 1; j < indices.size(); j++)
                {
                    int u = indices[i];
                    int v = indices[j];
                    mp[u][v] = 1;
                    mp[v][u] = 1;
                }
            }
        }
    }

    // BFS 求最短路径
    int bfs(int startIdx, int endIdx, int totalWords)
    {
        if (startIdx == endIdx) return 1;
        
        vector<bool> visited(totalWords, false);
        queue<pair<int, int>> q; // {当前单词索引, 当前步数}
        
        q.push({startIdx, 1});
        visited[startIdx] = true;
        
        while (!q.empty())
        {
            auto [curr, steps] = q.front();
            q.pop();
            
            // 遍历所有可能的邻居
            for (int next = 0; next < totalWords; next++)
            {
                if (mp[curr][next] == 1 && !visited[next])
                {
                    if (next == endIdx)
                        return steps + 1;
                    
                    visited[next] = true;
                    q.push({next, steps + 1});
                }
            }
        }
        
        return 0; // 无法到达
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        // 1. 检查 endWord 是否在 wordList 中
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord) == dict.end())
            return 0;
        
        // 2. 构建单词列表：beginWord + wordList
        vector<string> allWords;
        allWords.push_back(beginWord);
        for (const string& w : wordList)
        {
            // 避免重复添加 beginWord（如果它在 wordList 中）
            if (w != beginWord)
                allWords.push_back(w);
        }
        
        int n = allWords.size();
        unordered_map<string, int> wordToIdx;
        
        // 3. 建立单词到索引的映射
        for (int i = 0; i < n; i++)
        {
            wordToIdx[allWords[i]] = i;
            buildGraph(allWords[i], i); // 构建通配符模式
        }
        
        // 4. 构建邻接矩阵
        buildAdjMatrix(n);
        
        // 5. 获取起始和目标索引
        int startIdx = wordToIdx[beginWord];
        int endIdx = wordToIdx[endWord];
        
        // 6. BFS 求最短路径
        return bfs(startIdx, endIdx, n);
    }
};

代码具体解析都在注释里，这个题目最麻烦的是怎么想到处理两个string是否只相差是一个字符，此处我们使用哈希表来建立。通过将string的每一个字符替换成'*'来存入哈希表中，再根据哈希表来建立图。图建好之后就是一个简单的bfs最短路径问题。

4.2 冗余连接 II​

link:冗余连接 II 解答代码如下：

class Solution {
public:
    struct UnionFind {
        vector<int> parents;
        UnionFind(int n) {
            parents.resize(n + 1); // 节点从 1 开始
            for (int i = 0; i <= n; ++i) parents[i] = i;
        }
        int find(int x) {
            if (parents[x] != x) parents[x] = find(parents[x]);
            return parents[x];
        }
        bool unite(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) return false; // 形成环
            parents[rootY] = rootX;
            return true;
        }
    };

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> inDegree(n + 1, 0);
        
        // 1. 统计入度
        for (const auto& edge : edges) {
            inDegree[edge[1]]++;
        }

        // 2. 查找入度为 2 的节点对应的两条边
        vector<int> candidate1, candidate2;
        if (true) { // 作用域块，方便查找
            for (const auto& edge : edges) {
                if (inDegree[edge[1]] == 2) {
                    if (candidate1.empty()) {
                        candidate1 = edge;
                    } else {
                        candidate2 = edge;
                        break; 
                    }
                }
            }
        }

        // 3. 如果存在入度为 2 的节点
        if (!candidate2.empty()) {
            // 尝试删除 candidate2 (后出现的那条)
            UnionFind uf(n);
            for (const auto& edge : edges) {
                if (edge == candidate2) continue; // 跳过这条边
                if (!uf.unite(edge[0], edge[1])) {
                    // 如果跳过 candidate2 后仍然有环，说明 candidate2 不是冗余边，必须删 candidate1
                    return candidate1;
                }
            }
            // 如果跳过 candidate2 后没有环，说明 candidate2 就是答案
            return candidate2;
        }

        // 4. 如果不存在入度为 2 的节点，说明是纯粹成环的情况 (类似 LC 684)
        UnionFind uf(n);
        for (const auto& edge : edges) {
            if (!uf.unite(edge[0], edge[1])) {
                return edge;
            }
        }
        
        return {}; // 理论上不会到这里
    }
};

这题和多余的边类似，只是从无向图变成了有向的。但是这个题目多了一些要注意的地方，无向图只用考虑成环的问题，有向图需要额外考虑一个入度的问题，当入度为2时，说明多余的边已经出现了。这个时候要将其处理掉。