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:
Optimal Subsequences (Hard Version)
Not Same
Cow and Snacks
Knight Tournament
Rectangles and Square
Three Problems
Bash Plays with Functions
Marvolo Gaunt's Ring
Golden System
Fibonacci Numbers
New Year and Hurry
Divide Points
D´Esopo-Pape algorithm
Fence Planks
Paint the String
Independent Set
Beautiful Mirrors with queries
Amity Assessment
Another One Bites The Dust
Foo Fighters
Giải Thuật Và Lập Trình - Lê Minh Hoàng
Table Compression
Arbitrary-Precision Arithmetic
Breadth-first search
Poster
Check if point belongs to the convex polygon in $O(\log N)$
Ant colony
Break Up
Edge Weight Assignment
Game with Chips
Treasure
New Year and the Treasure Geolocation