AND Graph CodeForces - 987F (状压)

链接

大意:给定$m$个数, 若$x\&y=0$, 则在$x$与$y$之间连一条无向边. 求无向图的连通块个数

暴力连边显然超时的, 可以通过辅助结点优化连边, 复杂度$O(n2^n)$

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <queue>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define pb push_back

using namespace std;

const int N = 1<<22;

int n, m;

int a[N], vis[N], f[N];

int main() {

	scanf("%d%d", &n, &m);

	REP(i,1,m) scanf("%d",a+i),f[a[i]]=1;

	int mx = (1<<n)-1, ans = 0;

	REP(i,1,m) if (!vis[a[i]]) {

		++ans;

		queue<int> q;

		q.push(a[i]);

		while (q.size()) {

			int x = q.front();q.pop();

			if (vis[x]) continue;

			vis[x] = 1;

			if (f[x]) q.push(mx^x);

			for (int y=x; y; y^=y&-y) q.push(x^y&-y);

		}

	}

	printf("%d\n", ans);

}