Codeforces Round #485 (Div. 1) C. AND Graph

原题链接.

题目大意:

给出m个小于2^n的数。

若u&v=0,则u,v之间有边。

问联通块个数。

1<=n<=22

题解:

考虑从一个点出发,找到与它&=0的。

假设它是x。

则可行点y的集合是x的所有子集的补集。

这样的话建一些辅助点,打个记忆化标记一下,就可以遍历联通块了。

复杂度 O ( 2 n n )

Code:

#include<cstdio>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;

const int N = 1 << 22;

int n, m, a[N + 5], bx[N * 2 + 5], bz[N * 2 + 5], ans, a2[26];

void dfs(int x) {
    if(bz[x]) return;
    bz[x] = 1;
    if(x < N) {
        dfs(x + N);
    } else {
        if(bx[a2[n] - 1 - (x - N)]) dfs(a2[n] - 1 - (x - N));
        fo(i, 0, n - 1) if(!(x & a2[i]))
            dfs(x | a2[i]);
    }
}

int main() {
    a2[0] = 1; fo(i, 1, 25) a2[i] = a2[i - 1] * 2;
    scanf("%d %d", &n, &m);
    fo(i, 1, m) scanf("%d", &a[i]), bx[a[i]] = 1;
    fo(i, 1, m) if(!bz[a[i]]) {
        dfs(a[i]); ans ++;
    }
    printf("%d", ans);
}
相关文章
相关标签/搜索