Codeforces Round #485 (Div. 2) F. AND Graph

题目连接：

http://codeforces.com/contest/987/problem/F

Description

You are given a set of size $m$ with integer elements between $0$ and $2^{n}-1$ inclusive. Let's build an undirected graph on these integers in the following way: connect two integers $x$ and $y$ with an edge if and only if $x \& y = 0$. Here $\&$ is the bitwise AND operation. Count the number of connected components in that graph.

Sample Input

2 3

1 2 3

Sample Output

2

题意

有n个点，每个点有一个值x，如果\(x&y=0\)，则两点之间连一条边，问最后有多少联通块

There are n point, each point has its value. If \(x&y=0\), connect the two point with a edge. Print the number of connected components.

题解：

考虑最暴力的，对于一个数，枚举出所有求位运算和后使他为0的数字，然后判断该数字存在与否。这样会导致很多无用枚举。反向思考，该点能排除哪些点呢？对于\(2^{22}\)所有数字搜一次，最多只搜一次，时间在上限之内。

Consider a number X. If we figure out the all number which make \(X&number=0\). It's too complex. If we add this number, it can exclude the number . So the number will be search for at most once.

代码

#include <bits/stdc++.h>

using namespace std;

int n, m, ans;

bool vis[1 << 22];

bool ext[1 << 22];

int x;

vector<int> v;

inline void dfs(int k) {

    if (vis[k]) return;

    vis[k] = 1;

    if (ext[k]) dfs(k ^ ((1 << n) - 1));

    for (int i = 0; i < n; i++)

        if (k & (1 << i)) dfs(k ^ (1 << i));

}

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

    cerr.tie(nullptr);

    cin >> n >> m;

    for (int i=0;i<m;i++) {

        cin>>x;

        v.push_back(x);

        ext[x]=1;

    }

    for (auto i:v) {

        if (!vis[i]) {

            ans++;

            vis[i] = 1;

            dfs(i ^ ((1 << n) - 1));

        }

    }

    cout << ans << endl;

}