src/graph/maximal_independent_set.hpp

• View this file on GitHub
• Last update: 2025-12-30 15:03:15+09:00
• Include: #include "src/graph/maximal_independent_set.hpp"

Depends on

• src/template.hpp

Verified with

• src/test/yosupo_maximum_independent_set.cpp

Code

#pragma once
#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;
    int md=-1;
    rep(i,n) if(!d[i]){
        if(g[i].count()<=1){
            v=i;
            break;
        }
        if(chmax(md,(int)g[i].count())){
            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(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/graph/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;
    int md=-1;
    rep(i,n) if(!d[i]){
        if(g[i].count()<=1){
            v=i;
            break;
        }
        if(chmax(md,(int)g[i].count())){
            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;
}

Back to top page