用近似算法求解顶点覆盖问题C++代码

以下是使用贪心算法求解顶点覆盖问题的C++代码：

#include <iostream>
#include <vector>
#include <set>

using namespace std;

// 顶点覆盖问题的近似算法
set<int> vertex_cover(const vector<pair<int, int>>& edges) {
    set<int> cover; // 记录顶点覆盖集合
    set<int> used; // 记录已经覆盖的边
    for (auto& e : edges) {
        if (used.count(e.first) || used.count(e.second)) {
            continue; // 如果这条边已经被覆盖了，则跳过
        }
        cover.insert(e.first); // 将这条边的两个端点都加入到集合中
        cover.insert(e.second);
        used.insert(e.first); // 标记这条边已经被覆盖了
        used.insert(e.second);
    }
    return cover;
}

int main() {
    // 构造一个图
    vector<pair<int, int>> edges = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 6}};
    // 求解顶点覆盖问题
    set<int> cover = vertex_cover(edges);
    // 输出结果
    cout << "Vertex cover: ";
    for (auto& v : cover) {
        cout << v << " ";
    }
    cout << endl;
    return 0;
}

这段代码使用了STL中的set容器来记录顶点覆盖集合和已经覆盖的边。时间复杂度为O(mlogn)，其中m为边的数量，n为顶点的数量。