graph/maximum-independent-set.hpp

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

Depends on

graph/graph-template.hpp

Required by

Code

#pragma once

#include "graph-template.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 2 "graph/maximum-independent-set.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 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;
}