Codeforces986C AND Graph 【位运算】【dfs】

题目大意：

一张$ m $个编号互异点图，最大不超过$ 2^n $，若两个编号位与为0则连边，问连通块数量。

题目分析：

考虑怎样的两个点会连边。这种说法对于A和B两个点来说，就相当于B在A的0的子集中。我们不妨将A的0用1填充，得到的每一个数取反都是可以与A连边的点，然后这个取反前的数也可以继续填充。重新审视它发现我们从小到大地考虑每个0被1填充是没关系的，因为我们很显然地遍历了所有情况。那么可以做记忆化。时间复杂度$O(n2^n)$.

代码：

 #include<bits/stdc++.h>
 using namespace std; const int maxn = ; int n,m,ans;
 int a[maxn],app[maxn];
 int arr[maxn][]; void dfs(int now,int dr){
     if(arr[now][dr] == ) return;
     arr[now][dr] = ;
     for(int i=;i<n;i++){
     if(((<<i) & now) == ){
         dfs(now|(<<i),dr);
     }
     }
     if(app[(<<n)--now]) arr[(<<n)--now][] = ,dfs((<<n)--now,);
 } void work(){
     for(int i=;i<=m;i++){
     if(!arr[a[i]][]){
         ans++;arr[a[i]][] = ;
         dfs(a[i],);
     }
     }
 } int main(){
     scanf("%d%d",&n,&m);
     for(int i=;i<=m;i++) scanf("%d",&a[i]),app[a[i]] = ;
     work();
     printf("%d",ans);
     return ;
 }