cf987f AND Graph

#include <iostream>

#include <cstdio>

using namespace std;

int n, uu, m;

bool a[4500005], vis[4500005][2];

void dfs(int x, int y){

	if(vis[x][y])	return ;

	vis[x][y] = true;

	if(y==1)	dfs(x, 2);

	else{

		for(int i=0; i<n; i++)

			if(!(x&(1<<i)))

				dfs(x|(1<<i), 2);

		if(a[(1<<n)-1-x])	dfs((1<<n)-1-x, 1);

	}

}

int main(){

	cin>>n>>m;

	for(int i=1; i<=m; i++){

		scanf("%d", &uu);

		a[uu] = true;

	}

	int ans=0;

	for(int i=0; i<(1<<n); i++)

		if(a[i] && !vis[i][1]){

			dfs(i, 1);

			ans++;

		}

	cout<<ans<<endl;

	return 0;

}

巴特西

cf987f AND Graph

最新文章

热门文章