src/maximal_independent_set.hpp

View this file on GitHub
Last update: 2025-10-08 00:44:44+09:00
Include: #include "src/maximal_independent_set.hpp"

Depends on

src/template.hpp

Verified with

src/test/yosupo_maximum_independent_set.cpp

Code

#include "template.hpp"

using BS = bitset<40>;
BS maximal_independent_set(vector<BS> g, BS d = 0) {
    int n = si(g);
    BS ret = 0;
    int v = -1;
    rep(i, n) if(!d[i]) v = i;
    if(v == -1) return ret;

    d[v] = 1;
    rep(i, n) g[i][v] = 0;
    if(g[v].count() > 1) {
        BS vs = maximal_independent_set(g, d);
        if(ret.count() < vs.count()) ret = vs;
    }
    rep(i, n) if(g[v][i]) {
        d[i] = 1;
        rep(j, n) g[j][i] = 0;
    }
    BS vs = maximal_independent_set(g, d);
    vs[v] = 1;
    if(ret.count() < vs.count()) ret = vs;
    return ret;
}

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 2 "src/maximal_independent_set.hpp"

using BS = bitset<40>;
BS maximal_independent_set(vector<BS> g, BS d = 0) {
    int n = si(g);
    BS ret = 0;
    int v = -1;
    rep(i, n) if(!d[i]) v = i;
    if(v == -1) return ret;

    d[v] = 1;
    rep(i, n) g[i][v] = 0;
    if(g[v].count() > 1) {
        BS vs = maximal_independent_set(g, d);
        if(ret.count() < vs.count()) ret = vs;
    }
    rep(i, n) if(g[v][i]) {
        d[i] = 1;
        rep(j, n) g[j][i] = 0;
    }
    BS vs = maximal_independent_set(g, d);
    vs[v] = 1;
    if(ret.count() < vs.count()) ret = vs;
    return ret;
}