C. AND Graph+dfs
程序员文章站
2022-06-09 19:01:24
...
每次dfs尝试所有可能相连的状态
C. AND Graph
time limit per test
4 secondsmemory limit per test
256 megabytesinput
standard inputoutput
standard outputYou are given a set of size m
is the bitwise AND operation. Count the number of connected components in that graph.
Input
In the first line of input there are two integers n
).
In the second line there are m
integers a1,a2,…,am (0≤ai<2n) — the elements of the set. All aiare distinct.
Output
Print the number of connected components.
Examples
Input
Copy
2 3 1 2 3
Output
Copy
2
Input
Copy
5 5 5 19 10 20 12
Output
Copy
2
Note
Graph from first sample:
Graph from second sample:
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
/*
ll pw(ll a, ll b) {
ll ans = 1; while (b) {
while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
ans = (ans * a) % MOD, --b;
} return ans;
}
*/
int msk;
int n, m;
int fl[1 << 22];
int was[1 << 22];
void dfs1(int v, int c) {
if (c == 0) {
fl[v] = 0;
if (!was[msk - v])
dfs1(msk - v, 1);
}
else {
was[v] = 1;
if (fl[v])
dfs1(v, 0);
for (int i = 0; i < n; ++i) {
int x = v & (msk - (1 << i));
if (!was[x])
dfs1(x, 1);
}
}
}
int main() {
freopen("in.txt","r",stdin);
cin >> n >> m;
msk = (1 << n) - 1;
for (int i = 0; i < m; ++i) {
int x;
cin >> x;
fl[x] = 1;
}
int ans = 0;
for (int i = 0; i < (1 << 22); ++i) {
if (fl[i]) {
dfs1(i, 0), ++ans;
}
}
cout << ans << "\n";
return 0;
}
上一篇: php数组去重实例及分析
下一篇: 单片机 定时器/计数器
推荐阅读
-
c. 求阶乘和的方法(N的值不能太大)初学者
-
C.进程调度实例讲解
-
codeforces C. Count Triangles
-
Codeforces 1355 C. Count Triangles
-
codeforces C. K-th Not Divisible by n
-
Robert C. Martin对RoR的高度评价令我吃惊
-
VK Cup 2017 - Qualification 1 C. Cycle In Maze(bfs+最短路+贪心+思维)
-
VK Cup 2017 - Qualification 2 C. Online Courses In BSU(dfs)
-
Codeforces Round #320 (Div. 2) C. A Problem about Polyline ( 数学 )
-
Codeforces Round #654 (Div. 2)-C. A Cookie for You