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

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;
}
上一篇:ofstream的问题


下一篇:Linux mount挂载磁盘报错 mount: wrong fs type, bad option, bad superblock on /dev/vdb