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.
Input
In the first line of input there are two integers $n$ and $m$ ($0 \le n \le 22$, $1 \le m \le 2^{n}$).
In the second line there are $m$ integers $a_1, a_2, \ldots, a_m$ ($0 \le a_{i} < 2^{n}$) — the elements of the set. All $a_{i}$ are distinct.
Output
Print the number of connected components.
Examples
input
2 3
1 2 3
output
2
input
5 5
5 19 10 20 12
output
2
Note
Graph from first sample:

Graph from second sample:

Solution:
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> was(1 << n, 1); for (int i = 0; i < m; i++) { int x; cin >> x; was[x] = 0; } vector<int> used(1 << n, 0); vector<int> que(1 << n); vector<int> inner(1 << n); int ans = 0; for (int start = 0; start < (1 << n); start++) { if (was[start]) { continue; } ans++; was[start] = 1; que[0] = start; int qs = 1; for (int q = 0; q < qs; q++) { int u = (1 << n) - 1 - que[q]; if (!used[u]) { used[u] = 1; inner[0] = u; int is = 1; for (int i = 0; i < is; i++) { int z = inner[i]; if (!was[z]) { was[z] = 1; que[qs++] = z; } for (int bit = 0; bit < n; bit++) { if ((z & (1 << bit)) && !used[z ^ (1 << bit)]) { used[z ^ (1 << bit)] = 1; inner[is++] = z ^ (1 << bit); } } } } } } cout << ans << '\n'; return 0; }
Related posts:
Wheels
Flowers and Chocolate
Ternary Search
Ordering Pizza
The Evil Temple and the Moving Rocks
Dream Team
Another One Bites The Dust
Load Testing
Rational Resistance
Rotate Columns (hard version)
Hate "A"
Arson In Berland Forest
Wilbur and Trees
Prefix-Suffix Palindrome (Easy version)
Primitive Root
Catalan Numbers
New Year and Permutation
Magical Boxes
Balanced Ternary
Degenerate Matrix
D´Esopo-Pape algorithm
Traveling Around the Golden Ring of Berland
Learning and Improving Algorithm through contests - Antti Laaksonen
Stairs and Elevators
Dima and Two Sequences
Big Data
Grandfather Dovlet’s calculator
Suns and Rays
Search the subarray with the maximum/minimum sum
Little Artem and Time Machine
Nikita and stack
Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor