合并图中的线性顶点链(在C++中)

#include <iostream>
#include <vector>
#include <unordered_set>

// 图的表示
class Graph {
public:
    std::vector<std::unordered_set<int>> adjacencyList;

    Graph(int numVertices) {
        adjacencyList.resize(numVertices);
    }

    void addEdge(int src, int dest) {
        adjacencyList[src].insert(dest);
        adjacencyList[dest].insert(src);
    }
};

// 合并线性顶点链
Graph mergeLinearVertexChain(const Graph& graph, const std::vector<int>& linearVertexChain) {
    Graph mergedGraph = graph;

    for (int vertex : linearVertexChain) {
        if (vertex >= mergedGraph.adjacencyList.size()) {
            mergedGraph.adjacencyList.resize(vertex + 1);
        }
    }

    for (int i = 0; i < linearVertexChain.size() - 1; i++) {
        int src = linearVertexChain[i];
        int dest = linearVertexChain[i + 1];
        mergedGraph.addEdge(src, dest);
    }

    return mergedGraph;
}

int main() {
    // 创建一个示例图
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);

    // 创建一个示例线性顶点链
    std::vector<int> linearVertexChain = {3, 4, 2};

    // 合并线性顶点链
    Graph mergedGraph = mergeLinearVertexChain(graph, linearVertexChain);

    // 打印合并后的图的邻接表
    for (int i = 0; i < mergedGraph.adjacencyList.size(); i++) {
        std::cout << "Vertex " << i << ": ";
        for (int neighbor : mergedGraph.adjacencyList[i]) {
            std::cout << neighbor << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}