Codeforces 987F(DFS+二进制)

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

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

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

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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;
}

------ 本文结束 ------