给定(m)个(0)~(2^n-1)的整数 ,每个整数代表一个点,两个整数(x,y)之间有无向边联通当且仅当$ x&y=0 (
求无向图有多少个联通块
) n<=22 $
n<=22吼啊!
来自rainbowcat的题解
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int n,m;
int a[1<<22],p[1<<22];
bool vis[1<<22];
void dfs(int x){
vis[x]=1;
for(int i=0;i<n;i++) {
if(!(x&(1<<i))&&(!vis[x^(1<<i)])) {dfs(x^(1<<i));}
if(a[x^(1<<n)-1]&&!vis[x^(1<<n)-1]) dfs(x^(1<<n)-1);
}
}
int ans=0;
int main(){
cin>>n>>m;
for(int i=1,x;i<=m;i++) {
scanf("%d",&p[i]);
a[p[i]]=1;
}
for(int i=1;i<=m;i++)
if(!vis[p[i]^(1<<n)-1]){ans++;if(!vis[p[i]]) dfs(p[i]);}
cout<<ans;
}