Codeforces 987F(DFS+二进制)

Codeforces 987F
题意：给定一个大小为$m$的集合，每一个数都在$[0 ,2^n−1]$，如果两个数$x,y$满足x&y=0就连一条无向边，问这$m$个数连成的图有多少个连通分量。

对于一个数，它$n$位取反的二进制数上删除一些1都可以和这个数连边。所以我们就 DFS 枚举每个数取反之后删掉哪些1，如果又找到另一个集合中的数就做一样的操作。一次 DFS 就相当于找一个连通分量。

知识点：二进制问题，可以取反等操作来简化问题，并且连通分量可以用 DFS 进行求解。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, m, vis[(1 << 22) + 10], whw[(1 << 22) + 10];
void dfs(int x) {
    if (vis[x]) return ;
    vis[x] = 1;
    if (whw[x]) dfs((1 << n) - 1 - x);
    for (int i = 0; i < n; i++) {
        if ((1 << i) & x) {
            dfs(x ^ (1 << i));
        }
    }
}
void clean() {
    ms(vis, 0), ms(whw, 0);
}
int solve() {
    clean();
    scanf("%d%d", &n, &m);
    for (int a, i = 1; i <= m; i++) scanf("%d", &a), whw[a] = 1;
    if (whw[(1 << n)]) return printf("1\n"), 0;
    int ans = 0;
    for (int i = 0; i <= (1 << n); i++) {
        if (!whw[i] || vis[i]) continue;
        dfs((1 << n) - 1 - i);
        ans++;
    }
    printf("%d\n", ans);
    return 0; 
}
int main() {
    solve();
    return 0;
}