AND Graph (Codeforces 986C)
Tags: Others, dsu

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.

Note: Graph from first sample:Graph from second sample:

Sample Inputs:
2 3
1 2 3

5 5
5 19 10 20 12

Sample Outputs:
2

2

Solution (Python):
import sys
inp = list(map(int, sys.stdin.buffer.read().split()))
(n, m) = inp[:2]
a = set(inp[2:])
y = 2 ** n
mk = [0] * (2 * y)
cur = 0
for x in a:
    if mk[x]:
        continue
    mk[x] = 1
    st = [x]

    def push(v):
        if not mk[v]:
            mk[v] = 1
            st.append(v)
    while st:
        u = st.pop()
        if u < y:
            push(y + u)
        else:
            for b in range(n):
                v = u | 1 << b
                push(v)
            v = y - 1 - (u - y)
            if v in a:
                push(v)
    cur += 1
print(cur)

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from typing import *
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
(n, m) = MII()
nums = LII()
used = [0] * (1 << n + 1)
sep = 1 << n
for num in nums:
    used[num + sep] = 1
del nums
ans = 0
for i in range(sep, sep * 2):
    if used[i]:
        ans += 1
        used[i] = 0
        stack = [i]
        while stack:
            u = stack.pop()
            if u >= sep:
                v = u - sep
                if not used[v]:
                    used[v] = 1
                    stack.append(v)
            else:
                for i in range(n):
                    if 1 << i & u == 0:
                        v = 1 << i | u
                        if not used[v]:
                            used[v] = 1
                            stack.append(v)
                v = sep - 1 - u + sep
                if used[v] == 1:
                    used[v] = 0
                    stack.append(v)
print(ans)

Solution (Python):
(n, m) = map(int, input().split())
a = set(map(int, input().split()))
y = 2 ** n
mk = [0] * (2 * y)
cur = 0
for x in a:
    if mk[x]:
        continue
    mk[x] = 1
    st = [x]

    def push(v):
        if not mk[v]:
            mk[v] = 1
            st.append(v)
    while st:
        u = st.pop()
        if u < y:
            push(y + u)
        else:
            for b in range(n):
                v = u | 1 << b
                push(v)
            v = y - 1 - (u - y)
            if v in a:
                push(v)
    cur += 1
print(cur)