「CF987F」 AND Graph - 建图

题目链接：传送门

Description

给定$m$个均小于$2^n$的数，其中若满足$x \& y = 0$则x和y之间有一条边。问连完所有边后连通块个数

Hint

$0 \leq n \leq 22, 1\leq m \leq 2^n$

Solution

套路建图题。 之前cxr大佬讲过一个类似的题目，思路差不多 总共建$m+2^n$个点，m个给出的点记为$(x,1)$，另外建$2^n$个点，记为$(x,2)$ 考虑这样连边：

对于所给的m个点从$(x,1)$ 连向 $(x,2)$

对于所有的x从$(x,2)$连向$(x|(1 << k),2)$，其中k满足x的第k位为0

对于所给的m个点从$(\sim x,2)$连向$(x,1)$ ~x为x在$2^n$意义下取反

证明比较显然，就不赘述了 不用真正把边都连出来，直接dfs即可

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = (1 << 22) + 1000;

int A[Maxn], P[Maxn], N, M, PP[Maxn];

inline void dfs (int x)
{
    int REV = ((1 << N) - 1) ^ x;
    if (P[REV]) return ;
    P[REV] = 1;
    if (PP[REV]) dfs(REV);
    for (int i = 0; i < N; ++i)
    {
        if (!(x & (1 << i)))
        {
            dfs(x | (1 << i));
        }
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("F.in", "r", stdin);
    freopen("F.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i){ scanf("%d", &A[i]); PP[A[i]] = 1;}
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        if (!P[A[i]])
        {
            ++cnt;
            dfs(A[i]);
        }
    }
    cout<<cnt<<endl;
    return 0;
}