半年前做的一道题现在还是不会

x&y=0

意味着，x的补集的子集都是和x直接相连的

不妨令图中的点数就是2^n

那么可以直接从x^((1<<n)-1)开始记忆化爆搜，路上遇到的都是和x直接相连的

如果遇到一个在给出集合里的数t，就从这个点额外再开一层，t^((1<<n)-1)再开始爆搜

这样，如果两个点直接或者间接相连，那么一定可以从任意一个点出发搜出整个连通块，并对每个点打上标记

总共的状态数是2^22。复杂度有保证

 

loc只是一个理解，其实不需要

#include
     
      using namespace std;const int N=(1<<22)+10;int exi[N];bool vis[N];// zuo i youwu visbool has[N];// you i youwu visint cnt,mx,len,up;int a[N];int n,m;void dfs(int x,int loc){    //cout<
      
       <<" now "<
       
        <
        
         >(lg[i-1]+1))?lg[i-1]+1:lg[i-1];*/    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++){        scanf("%d",&a[i]),exi[a[i]]=i,mx=max(mx,a[i]);    }    for(int i=0;i<=23;i++){        if((1<
         
          mx) break;        len=i+1;    }    up=(1<