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