CF 986C AND Graph

题目描述

https://www.luogu.com.cn/problem/CF986C

简要题意：给定一个长度为 $n$ 的序列 $a_i$，每个数的范围为 $[0,2^m-1]$，$x$ 和 $y$ 之间有一条无向边的条件为 $a_x$ 与 $a_y$ 的与为 $0$，求连通块个数

Solution

我们从每一个没到过的点开始 $dfs$，每次开始 $dfs$ 就代表有一个新的连通块

现在我们考虑什么情况下 $x~and~y=0$，当且仅当 $x$ 取反后，$y$ 是 $x$ 的子集，那么我们考虑将 $x$ 取反，然后每次扔一个 $1$，向下 $dfs$ 即可

#include <iostream>
#include <cstdio>
using namespace std;

int n, m, M, a[1 << 22];

bool vis[1 << 22], p[1 << 22];
void dfs(int v) {
    if (vis[v]) return ; vis[v] = 1; 
    for (int i = 0; i < n; ++i)
        if (v >> i & 1) dfs(v ^ 1 << i);
    if (p[v]) dfs(M ^ v); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; int ans = 0; M = (1 << n) - 1;
    for (int i = 1; i <= m; ++i) cin >> a[i], p[a[i]] = 1; 
    for (int i = 1; i <= m; ++i) 
        if (!vis[a[i]]) ++ans, dfs(M ^ a[i]);
    cout << ans << "\n"; 
    return 0;
}