给定一个无向图其中有两个连通块要求在两个连通块之间添加一条边使得原图中第一个顶点和最后一个顶点之间的最短路径最长。用C++实现

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

// 图的邻接表表示
class Graph {
private:
    int V; // 顶点数
    vector<vector<int>> adj; // 邻接表

public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // BFS遍历，返回最短路径长度
    int BFS(int src, int dest) {
        vector<bool> visited(V, false);
        vector<int> dist(V, 0);
        queue<int> q;

        visited[src] = true;
        q.push(src);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }

        return dist[dest];
    }

    // 寻找最长路径
    int findLongestPath() {
        int longestPath = 0;

        // 遍历每个顶点，计算到其他连通块的最短路径，取最大值
        for (int i = 0; i < V; i++) {
            for (int j = i + 1; j < V; j++) {
                // 如果i和j不在同一个连通块中
                if (!isConnected(i, j)) {
                    int shortestPath = BFS(i, j);
                    longestPath = max(longestPath, shortestPath);
                }
            }
        }

        return longestPath;
    }

    // 判断两个顶点是否在同一个连通块中
    bool isConnected(int u, int v) {
        vector<bool> visited(V, false);
        DFS(u, visited);
        return visited[v];
    }

    // DFS遍历
    void DFS(int v, vector<bool>& visited) {
        visited[v] = true;
        for (int u : adj[v]) {
            if (!visited[u]) {
                DFS(u, visited);
            }
        }
    }
};

int main() {
    int V = 6;
    Graph g(V);

    // 添加边
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(4, 5);

    int longestPath = g.findLongestPath();
    cout << "最长路径长度: " << longestPath << endl;

    return 0;
}
``