Artifact Content
Not logged in

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;
}