codeforces CF986C AND Graph 建圖 dfs

博客迁移计划15

$ \rightarrow $ 戳我進CF原題

C. AND Graph


time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

 
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, \dots ,a_m ( 0 \le a_i \le 2^n ) $ — the elements of the set.
All $ a_i $ are distinct.
 

Output

Print the number of connected components.

 

Examples

input1

 2 3
 1 2 3

output1

2

input2

 5 5
 5 19 10 20 12

output2

2

 

Note

Graph from first sample:

codeforces CF986C AND Graph 建圖 dfs

Graph from second sample:

codeforces CF986C AND Graph 建圖 dfs

 

題目大意

  • 給定 $ m $ 個 $ 0 ~ 2^n-1 $ 之間的整數,每個整數代表一個點

  • 兩個整數 $ x,y $ 之間有無向邊當且僅當 $ x $ & $ y=0 $ ,求無向圖有多少個連通塊

  • $ n \le 22 $

 

題解

  • 把 $ 0 ~ 2^n-1 $ 之間的每個點拆成 $ x $ 和 $ x' $ 兩個點

  • $ 1. $ 從 $ x $ 到 $ (~x)' $ 連有向邊

  • $ 2. $ 從 $ x' $ 到 $ (x \quad xor \quad (1 \ll k ))' $ 連有向邊 $ (o \le k < n ) $

  • $ 3. $ 若 $ x $ 屬於給定的 $ m $ 個數,則從 $ x' $ 到 $ x $ 連有向邊

  • 從 $ m $ 個數出發進行遍歷,求連通塊數

 

代碼

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn (1<<23)+5
int n,m,ans,tot;
bool vis[maxn],mark[maxn];
void dfs(int u){
    if(vis[u]) return; vis[u]=1;
    if(u<(1<<n)) dfs(u+(1<<n));
    else {
        tot=(1<<(n+1))-1-u;
        if(!vis[tot]&&mark[tot]) dfs(tot);
        for(int i=0;i<n;++i) if(!vis[u|(1<<i)]) dfs(u|(1<<i));
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int x,i=1;i<=m;++i){ scanf("%d",&x); mark[x]=1; }
    for(int i=0;i<(1<<n);++i) 
        if(mark[i]&&!vis[i]){ ++ans; dfs(i); }
    printf("%d",ans);
    return 0;
}
/*
#        40059473
When     2018-07-07 14:30:49
Who      PotremZ
Problem  C - AND Graph
Lang     GNU C++
Verdict  Accepted
Time     764 ms
Memory   91100 KB
*/
上一篇:《算法竞赛进阶指南》0x42 T2 A Tiny Problem with Integers


下一篇:java类反射越过泛型检查