Artifact d654c32e904bdfb1716534f66c3bc6947841cc3f
//-------------------------------------------------------------
// Bruteforuce O(2^V) search with trivial edagari.
//
// |V| must be <= 63
//
// Verified by
// - SRM 679 Div1 Lv2
//-------------------------------------------------------------
int max_independent_set(const vector<vector<int>>& G)
{
const int N = G.size();
vector<LL> badmask(G.size());
for(int v=0; v<N; ++v) {
LL x = 1LL<<v;
for(int u: G[v])
x |= 1LL<<u;
badmask[v] = x;
}
int best = 0;
function<void(int,LL,int)> rec = [&](int v, LL rest, int cur) {
if(best < cur)
best = cur;
if(rest == 0)
return;
if(cur + __builtin_popcountll(rest) <= best)
return;
LL r1 = rest &~ (1LL<<v);
LL r2 = rest &~ badmask[v];
if(rest & (1LL<<v)) {
if(r1 != r2) rec(v+1, r1, cur);
rec(v+1, r2, cur+1);
} else {
rec(v+1, r1, cur);
}
};
rec(0, (1LL<<N)-1, 0);
return best;
}