graph/vertex-cover.hpp

• View this file on GitHub
• Last update: 2022-07-12 17:31:52+03:00
• Include: #include "graph/vertex-cover.hpp"

Depends on

• graph/graph-template.hpp
• graph/maximum-independent-set.hpp
• template/macro.hpp

Required by

• graph/vertex-cover-small-ans.hpp

Code

#pragma once

#include "graph-template.hpp"
#include "../template/macro.hpp"
#include "maximum-independent-set.hpp"

vector<int> vertexCover2(const UnweightedGraph &g) {
    int n = sz(g);
    vector<int> used(n, 1);
    auto is = maximumIndependentSet(g);
    for (int el : is) {
        used[el] = 0;
    }
    vector<int> ans;
    for (int i = 0; i < n; i++)
        if (used[i])
            ans.push_back(i);
    return ans;
}

void vertexCoverErase(vector<vector<bool>> &g, vector<int> &vs, int u) {
    int n = sz(g);
    for (int i = 0; i < n; i++) {
        if (i != u) {
            g[i].erase(g[i].begin() + u);
        }
    }
    vs.erase(vs.begin() + u);
    g.erase(g.begin() + u);
}

void vertexCoverClean(vector<vector<bool>> &g, vector<int> &vs) {
    int n = sz(g);
    for (int i = n - 1; i >= 0; i--) {
        int d = accumulate(all(g[i]), 0);
        if (d == 0)
            vertexCoverErase(g, vs, i);
    }
}

pair<int, vector<int>> vertexCoverAns(vector<vector<bool>> &g, int k, vector<int> &vs, vector<int> &cur_ans) {
    if (k < 0)
        return {1e9, {-1}};
    if (g.empty())
        return {0, cur_ans};
    if (k == 0)
        return {1e9, {-1}};
    int n = sz(g);
    vector<int> deg(n, 0);
    for (int i = 0; i < n; i++) {
        deg[i] = accumulate(all(g[i]), 0);
    }
    int w = 0;
    for (int i = 1; i < n; i++) {
        if (deg[w] < deg[i])
            w = i;
    }
    pair<int, vector<int>> ans = {1e9, {-1}};
    auto g1 = g;
    auto vs1 = vs;
    auto cur_ans1 = cur_ans;
    cur_ans1.push_back(vs[w]);
    vertexCoverErase(g1, vs1, w);
    vertexCoverClean(g1, vs1);
    auto ans1 = vertexCoverAns(g1, k - 1, vs1, cur_ans1);
    ans1.first++;
    ans = min(ans, ans1);
    auto g2 = g;
    auto vs2 = vs;
    auto cur_ans2 = cur_ans;
    for (int j = n - 1; j >= 0; j--) {
        if (g[w][j]) {
            vertexCoverErase(g2, vs2, j);
            cur_ans2.push_back(vs[j]);
        }
    }
    vertexCoverClean(g2, vs2);
    auto ans2 = vertexCoverAns(g2, k - deg[w], vs2, cur_ans2);
    ans2.first += deg[w];
    ans = min(ans, ans2);
    return ans;
}

vector<int> vertexCover(const UnweightedGraph &g, int k) {
    int n = sz(g);
    vector<vector<bool>> g2(n, vector<bool>(n));
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) {
            g2[i][j] = 1;
        }
    }
    vector<int> allvs(n);
    iota(all(allvs), 0);
    vector<int> cur_ans;
    auto ans = vertexCoverAns(g2, k, allvs, cur_ans);
    if (ans.first == 1000000000) {
        return {-1};
    }
    return ans.second;
}

#line 2 "graph/vertex-cover.hpp"

#line 2 "graph/graph-template.hpp"

using UnweightedGraph = vector<vector<int>>;

UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) {
    UnweightedGraph g((size_t)N);
    if (M == -1)
        M = N - 1;
    for (int _ = 0; _ < M; _++) {
        int x, y;
        cin >> x >> y;
        if (is_1origin) {
            x--;
            y--;
        }
        g[(size_t) x].push_back(y);
        if (!is_directed)
            g[(size_t) y].push_back(x);
    }
    return g;
}
#line 2 "template/macro.hpp"

#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sz(v) (int((v).size()))
#line 2 "graph/maximum-independent-set.hpp"

#line 4 "graph/maximum-independent-set.hpp"

vector<int> maximumIndependentSet(const UnweightedGraph &g) {
    assert(sz(g) <= 64);
    int n = sz(g);
    vector<ull> gb(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) {
            gb[i] |= 1ULL << j;
        }
        gb[i] |= 1ULL << i;
        gb[i] ^= ULLONG_MAX;
    }
    int k = (n + 1) / 2;
    unordered_map<ull, ull> memo;
    //vector<ull> memo(1ULL << k, ULLONG_MAX);
    auto rec = [&](auto rec, ull mask, int bit) -> ull {
        if (mask == 0)
            return 0;
        if (mask < (1ULL << k) && memo.find(mask) != memo.end()) {
            return memo[mask]; 
        }
        if (mask & (1ULL << bit)) {
            auto ans1 = rec(rec, mask ^ (1ULL << bit), bit - 1);
            auto ans2 = rec(rec, mask & gb[bit], bit - 1) | (1ULL << bit);
            if (__builtin_popcountll(ans1) < __builtin_popcountll(ans2)) {
                ans1 = ans2;
            }
            if (mask < (1ULL << k)) {
                memo[mask] = ans1;
            }
            return ans1;
        } else {
            return rec(rec, mask, bit - 1);
        }
    };
    auto ans = rec(rec, (1ULL << n) - 1, n - 1);
    vector<int> ans2;
    for (int i = 0; i < n; i++) {
        if (ans & (1ULL << i)) {
            ans2.push_back(i);
        }
    }
    return ans2;
}
#line 6 "graph/vertex-cover.hpp"

vector<int> vertexCover2(const UnweightedGraph &g) {
    int n = sz(g);
    vector<int> used(n, 1);
    auto is = maximumIndependentSet(g);
    for (int el : is) {
        used[el] = 0;
    }
    vector<int> ans;
    for (int i = 0; i < n; i++)
        if (used[i])
            ans.push_back(i);
    return ans;
}

void vertexCoverErase(vector<vector<bool>> &g, vector<int> &vs, int u) {
    int n = sz(g);
    for (int i = 0; i < n; i++) {
        if (i != u) {
            g[i].erase(g[i].begin() + u);
        }
    }
    vs.erase(vs.begin() + u);
    g.erase(g.begin() + u);
}

void vertexCoverClean(vector<vector<bool>> &g, vector<int> &vs) {
    int n = sz(g);
    for (int i = n - 1; i >= 0; i--) {
        int d = accumulate(all(g[i]), 0);
        if (d == 0)
            vertexCoverErase(g, vs, i);
    }
}

pair<int, vector<int>> vertexCoverAns(vector<vector<bool>> &g, int k, vector<int> &vs, vector<int> &cur_ans) {
    if (k < 0)
        return {1e9, {-1}};
    if (g.empty())
        return {0, cur_ans};
    if (k == 0)
        return {1e9, {-1}};
    int n = sz(g);
    vector<int> deg(n, 0);
    for (int i = 0; i < n; i++) {
        deg[i] = accumulate(all(g[i]), 0);
    }
    int w = 0;
    for (int i = 1; i < n; i++) {
        if (deg[w] < deg[i])
            w = i;
    }
    pair<int, vector<int>> ans = {1e9, {-1}};
    auto g1 = g;
    auto vs1 = vs;
    auto cur_ans1 = cur_ans;
    cur_ans1.push_back(vs[w]);
    vertexCoverErase(g1, vs1, w);
    vertexCoverClean(g1, vs1);
    auto ans1 = vertexCoverAns(g1, k - 1, vs1, cur_ans1);
    ans1.first++;
    ans = min(ans, ans1);
    auto g2 = g;
    auto vs2 = vs;
    auto cur_ans2 = cur_ans;
    for (int j = n - 1; j >= 0; j--) {
        if (g[w][j]) {
            vertexCoverErase(g2, vs2, j);
            cur_ans2.push_back(vs[j]);
        }
    }
    vertexCoverClean(g2, vs2);
    auto ans2 = vertexCoverAns(g2, k - deg[w], vs2, cur_ans2);
    ans2.first += deg[w];
    ans = min(ans, ans2);
    return ans;
}

vector<int> vertexCover(const UnweightedGraph &g, int k) {
    int n = sz(g);
    vector<vector<bool>> g2(n, vector<bool>(n));
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) {
            g2[i][j] = 1;
        }
    }
    vector<int> allvs(n);
    iota(all(allvs), 0);
    vector<int> cur_ans;
    auto ans = vertexCoverAns(g2, k, allvs, cur_ans);
    if (ans.first == 1000000000) {
        return {-1};
    }
    return ans.second;
}

Back to top page