Templates

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub AlexanderNekrasov/Templates

:warning: graph/vertex-cover-small-ans.hpp

Depends on

Code

#pragma once

#include "graph-template.hpp"
#include "graph-utils.hpp"
#include "bipartite-graph.hpp"
#include "../template/util.hpp"
#include "vertex-cover.hpp"

// Finds vertex cover on big graphs, where it is known that 
// size of vertex cover is small, works in O((n+m)log(n)+k^3+1.63^k)
// returns {-1} if vertex cover size is greater than k.
vector<int> vertexCoverSmallAns(UnweightedGraph g, int k) {
    int n = (int) g.size();
    // **Buss's reduction**
    // Every vertex with a degree > k should be in the vertex cover
    vector<int> ans;
    vector<char> used(n);
    for (int i = 0; i < n; i++) {
        if ((int) g[i].size() > k) {
            used[i] = 1;
            ans.push_back(i);
        }
    }
    // g2 = g \ ans \ { v \in V | deg v = 0 }
    vector<int> vs2;
    for (int i = 0; i < n; i++) {
        if (!used[i] && any_of(all(g[i]), [&](int v) { return !used[v]; }))
            vs2.push_back(i);
    }
    UnweightedGraph g2 = subgraph(g, vs2);
    for (auto &el : g2) {
        unq(el);
    }
    // Now g2 should contain at most k+k^2 vertices and at most k^2 edges
    {
        int cntEdges = 0;
        for (int i = 0; i < sz(g2); i++)
            cntEdges += g2[i].size();
        cntEdges >>= 1;
        if (sz(g2) > k + k * k || cntEdges > k * k) {
            return {-1};
        }
    }
    // Construct a solution to LP problem using vertex cover on bipartite graph 
    BipartiteGraph g3(sz(g2), sz(g2));
    for (int i = 0; i < sz(g2); i++) {
        for (int j : g2[i]) {
            g3.add_edge(i, j);
        }
    }
    auto vc_ = g3.minimumVertexCover();
    if (sz(vc_.first) + sz(vc_.second) > 2 * (k - sz(ans))) {
        return {-1};
    }
    vector<int> cnt(sz(g2));
    for (int v : vc_.first) {
        cnt[v]++;
    }
    for (int v : vc_.second) {
        cnt[v]++;
    }
    vector<int> v12;
    for (int i = 0; i < sz(g2); i++) {
        if (cnt[i] == 2) {
            ans.push_back(vs2[i]);
            used[i] = 1;
        } else if (cnt[i] == 1) {
            v12.push_back(i);
        }
    }
    auto g4 = subgraph(g2, v12);
    for (auto &el : g4) {
        unq(el);
    }
    assert(sz(g4) <= 2 * k);

    // Construct vertex cover on small graph
    auto ans2 = vertexCover(g4, k - sz(ans));
    // auto ans2 = vertexCover2(g4);
    if ((ans2.size() == 1 && ans2[0] == -1) || sz(ans2) > k - sz(ans)) {
        return {-1};
    }
    for (int el : ans2) {
        ans.push_back(vs2[v12[el]]);
    }

    // check that ans is vertex cover (not checking if it is minimum)
    used.assign(n, 0);
    for (int el : ans) {
        used[el] = 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) {
            assert(used[i] || used[j]);
        }
    }
    return ans;
}
#line 2 "graph/vertex-cover-small-ans.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 "graph/graph-utils.hpp"

#line 4 "graph/graph-utils.hpp"

UnweightedGraph subgraph(UnweightedGraph g, vector<int> vs) {
    sort(all(vs));
    UnweightedGraph g2(sz(vs));
    for (int i = 0; i < (int) vs.size(); i++) {
        for (int j : g[vs[i]]) {
            auto it = lower_bound(all(vs), j);
            if (it != vs.end() && *it == j) {
                g2[i].push_back(lower_bound(all(vs), j) - vs.begin());
            }
        }
    }
    return g2;
}
#line 2 "graph/bipartite-graph.hpp"

#line 2 "ds/queue.hpp"

template<typename T>
struct simple_queue {
    vector<T> arr;
    int pos = 0;
    void reserve(int n) { arr.reserve(n); }
    int size() const { return sz(arr) - pos; }
    bool empty() { return pos == sz(arr); }
    void push(const T& t) { arr.push_back(t); }
    T& front() {
        return arr[pos];
    }
    void clear() {
        arr.clear();
        pos = 0;
    }
    void pop() { pos++; }
};
#line 3 "graph/maxflow.hpp"

template<typename T>
struct MaxFlow {
    explicit MaxFlow(int n) : n(n), g(n) {}

    int add_edge(int from, int to, T cap) {
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        assert(0 <= cap);
        int m = sz(pos);
        pos.push_back({from, sz(g[from])});
        int sz_from = sz(g[from]);
        int sz_to = sz(g[to]);
        if (from == to) {
            sz_to++;
        }
        g[from].push_back({to, sz_to, cap});
        g[to].push_back({from, sz_from, 0});
        return m;
    }

    struct edge {
        int from, to;
        T cap, flow;
    };

    edge get_edge(int i) {
        assert(0 <= i && i < sz(pos));
        auto _e = g[pos[i].first][pos[i].second];
        auto _re = g[_e.to][_e.rev];
        return {_re.to, _e.to, _e.cap + _re.cap, _re.cap};
    }

    vector<edge> edges() {
        int m = sz(pos);
        vector<edge> ans;
        for (int i = 0; i < m; i++) {
            ans.push_back(get_edge(i));
        }
        return ans;
    }

    T flow(int s, int t) {
        return flow(s, t, numeric_limits<T>::max());
    }

    T flow(int s, int t, T flow_limit) {
        assert(0 <= s && s < n);
        assert(0 <= t && t < n);
        assert(s != t);
        vector<int> level(n), iter(n);
        simple_queue<int> q;

        auto bfs = [&]() {
            fill(all(level), -1);
            level[s] = 0;
            q.clear();
            q.push(s);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (auto e : g[v]) {
                    if (e.cap == 0 || level[e.to] >= 0) continue;
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    q.push(e.to);
                }
            }
        };
        auto dfs = [&](auto self, int v, T up) {
            if (v == s) {
                return up;
            }
            T res = 0;
            int level_v = level[v];
            for (int& i = iter[v]; i < sz(g[v]); i++) {
                auto &e = g[v][i];
                if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
                T d =
                    self(self, e.to, min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == up)
                    return res;
            }
            level[v] = n;
            return res;
        };

        T flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (level[t] == -1)
                break;
            fill(all(iter), 0);
            T f = dfs(dfs, t, flow_limit - flow);
            if (!f)
                break;
            flow += f;
        }
        return flow;
    }

    private:
    int n;
    vector<pair<int, int>> pos;
    struct _edge {
        int to, rev;
        T cap;
    };
    vector<vector<_edge>> g;
};
#line 4 "graph/bipartite-graph.hpp"

struct BipartiteGraph: MaxFlow<ll> {
    int L, R, s, t;
    bool was_flow;

    explicit BipartiteGraph(int N, int M)
        : MaxFlow<ll>(N + M + 2),
          L(N),
          R(M),
          s(N + M),
          t(N + M + 1),
          was_flow(false) {
        for (int i = 0; i < L; i++) {
            MaxFlow<ll>::add_edge(s, i, 1); 
        }
        for (int i = 0; i < R; i++) {
            MaxFlow<ll>::add_edge(i + L, t, 1);
        }
    }

    int add_edge(int a, int b, ll c = 1) {
        assert(0 <= a && a < L);
        assert(0 <= b && b < R);
        return MaxFlow<ll>::add_edge(a, b + L, c);
    }

    ll flow() {
        was_flow = true;
        return MaxFlow<ll>::flow(s, t);
    }

    pair<vector<int>, vector<int>> minimumVertexCover() {
        if (!was_flow)
            flow();
        vector<bool> used = dfsUsed();
        vector<int> lv, rv;
        for (int i = 0; i < L; i++) {
            if (!used[i]) {
                lv.push_back(i);
            }
        }
        for (int i = 0; i < R; i++) {
            if (used[i + L]) {
                rv.push_back(i);
            }
        }
        return {lv, rv};
    }

    private:
    vector<bool> dfsUsed() {
        vector<vector<int>> g(L + R);
        vector<bool> matched(L);
        for (auto &e : MaxFlow<ll>::edges()) {
            if (e.from == s || e.to == t)
                continue;
            if (e.flow > 0) {
                g[e.to].push_back(e.from);
                matched[e.from] = true;
            } else {
                g[e.from].push_back(e.to);
            }
        }
        vector<bool> used(L + R);
        auto dfs = [&](auto dfs, int v) -> void {
            used[v] = 1;
            for (int u : g[v])
                if (!used[u])
                    dfs(dfs, u);
        };
        for (int i = 0; i < L; i++) {
            if (!matched[i] && !used[i]) {
                dfs(dfs, i);
            }
        }
        return used;
    }
};
#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 3 "template/util.hpp"
#include <vector>
#include <algorithm>
#include <string>

template<typename T>
void unq(std::vector<T> &arr) {
    sort(all(arr));
    arr.erase(unique(all(arr)), arr.end());
}
void unq(std::string &arr) {
    sort(all(arr));
    arr.erase(unique(all(arr)), arr.end());
}
#line 2 "graph/vertex-cover.hpp"

#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;
}
#line 8 "graph/vertex-cover-small-ans.hpp"

// Finds vertex cover on big graphs, where it is known that 
// size of vertex cover is small, works in O((n+m)log(n)+k^3+1.63^k)
// returns {-1} if vertex cover size is greater than k.
vector<int> vertexCoverSmallAns(UnweightedGraph g, int k) {
    int n = (int) g.size();
    // **Buss's reduction**
    // Every vertex with a degree > k should be in the vertex cover
    vector<int> ans;
    vector<char> used(n);
    for (int i = 0; i < n; i++) {
        if ((int) g[i].size() > k) {
            used[i] = 1;
            ans.push_back(i);
        }
    }
    // g2 = g \ ans \ { v \in V | deg v = 0 }
    vector<int> vs2;
    for (int i = 0; i < n; i++) {
        if (!used[i] && any_of(all(g[i]), [&](int v) { return !used[v]; }))
            vs2.push_back(i);
    }
    UnweightedGraph g2 = subgraph(g, vs2);
    for (auto &el : g2) {
        unq(el);
    }
    // Now g2 should contain at most k+k^2 vertices and at most k^2 edges
    {
        int cntEdges = 0;
        for (int i = 0; i < sz(g2); i++)
            cntEdges += g2[i].size();
        cntEdges >>= 1;
        if (sz(g2) > k + k * k || cntEdges > k * k) {
            return {-1};
        }
    }
    // Construct a solution to LP problem using vertex cover on bipartite graph 
    BipartiteGraph g3(sz(g2), sz(g2));
    for (int i = 0; i < sz(g2); i++) {
        for (int j : g2[i]) {
            g3.add_edge(i, j);
        }
    }
    auto vc_ = g3.minimumVertexCover();
    if (sz(vc_.first) + sz(vc_.second) > 2 * (k - sz(ans))) {
        return {-1};
    }
    vector<int> cnt(sz(g2));
    for (int v : vc_.first) {
        cnt[v]++;
    }
    for (int v : vc_.second) {
        cnt[v]++;
    }
    vector<int> v12;
    for (int i = 0; i < sz(g2); i++) {
        if (cnt[i] == 2) {
            ans.push_back(vs2[i]);
            used[i] = 1;
        } else if (cnt[i] == 1) {
            v12.push_back(i);
        }
    }
    auto g4 = subgraph(g2, v12);
    for (auto &el : g4) {
        unq(el);
    }
    assert(sz(g4) <= 2 * k);

    // Construct vertex cover on small graph
    auto ans2 = vertexCover(g4, k - sz(ans));
    // auto ans2 = vertexCover2(g4);
    if ((ans2.size() == 1 && ans2[0] == -1) || sz(ans2) > k - sz(ans)) {
        return {-1};
    }
    for (int el : ans2) {
        ans.push_back(vs2[v12[el]]);
    }

    // check that ans is vertex cover (not checking if it is minimum)
    used.assign(n, 0);
    for (int el : ans) {
        used[el] = 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) {
            assert(used[i] || used[j]);
        }
    }
    return ans;
}
Back to top page