Codeforces #485 C. AND Graph

これはよい問題かも。
http://codeforces.com/contest/986/problem/C

問題

M個の頂点からなるグラフがある。
各頂点には異なる非負整数が設定されている。
ここで、XとYが設定された２頂点の間は、X and Y==0の場合のみ辺が貼られるとする。
このグラフは何個の連結成分からなるかを答えよ。

解法

辺の数がO(M^2)程度になるケースもあるので、愚直に辺を列挙するのは無謀である。
ある未訪問点Xを含む連結成分を順にたどることを考えよう。
条件より、Xに対し辺をはる頂点Yは~Xのsubmaskでなければならない。

よって~XのsubmaskをDFSの要領で列挙しよう。
その際、未訪問点Yが見つかったらそれをXの連結成分として追加していく。
Xのsubmaskを列挙し終わったら、同様にYのsubmaskを列挙…と繰り返す。

その際、いったん探索したbitmaskのパターンは再度探索してもしょうがないので、メモ化再帰の要領で探索を打ち切ろう。

int N,M;
int A[1<<22];
int S[1<<22];
vector<int> V;

void dfs(int v) {
	if(S[v]==1) return;
	S[v]=1;
	if(A[v]) {
		V.push_back(v);
		A[v]=0;
	}
	int i;
	FOR(i,22) if(v&(1<<i)) dfs(v^(1<<i));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,M) {
		scanf("%d",&x);
		A[x]=1;
	}
	
	int ret=0;
	FOR(i,1<<22) if(A[i]) {
		ret++;
		V.push_back(i);
		while(V.size()) {
			x=V.back();
			V.pop_back();
			dfs(x^((1<<22)-1));
		}
	}
	cout<<ret<<endl;
	
}

まとめ

シンプルな問題設定でいいね。