點擊打開鏈接

F. AND Graph

time limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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<2^n$)?— the elements of the set. All $a_i$

are distinct.

Output

Print the number of connected components.

ExamplesInputCopy2 3 1 2 3 OutputCopy2 InputCopy5 5 5 19 10 20 12 OutputCopy2 Note

Graph from first sample:

Graph from second sample:

題意：

給出m個大于等于0且小于2^n的不同的整數，如果兩個數$x\&y=0$，就把這兩個數連接起來，問有多少個連通分支？

錯誤思路：

并查集，將這m個數兩兩相與，$\mathrm{若x}\&y=\mathrm{0，則把這兩個數放到一個集合，然后標記這m個數的根節點，}$

$\mathrm{最后統計根節點的個數，即連通分支的個數。顯然，m非常大時，必定超時}$

超時代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=(1<<22)+5; int fa[maxn]; int find(int x) {if(fa[x]==x) return x;return fa[x]=find(fa[x]); } void mix(int x,int y) {int fx=find(x),fy=find(y);fa[fy]=fx; } int n,m,a[maxn]; bool vis[maxn]; int main() {while(scanf("%d%d",&n,&m)!=EOF){bool flag=0;for(int i=0;i<m;i++){scanf("%d",&a[i]);if(a[i]==0)flag=1;}if(flag){printf("1\n");continue;}for(int i=0;i<=(1<<n);i++)fa[i]=i;memset(vis,0,sizeof(vis));for(int i=0;i<m;i++)for(int j=i+1;j<m;j++){if((a[i]&a[j])==0){mix(a[i],a[j]);//printf("%d %d\n",a[i],a[j]);}}for(int i=0;i<m;i++){//printf("%d\n",find(a[i]));vis[find(a[i])]=1;}int ans=0;//for(int i=0;i<=(1<<n);i++)for(int i=0;i<m;i++)if(vis[a[i]])ans++;printf("%d\n",ans);}return 0; }正確思路： x有邊連出的一定是 (2^n-1) ^ x 的一個子集，直接連子集復雜度是n^2,但是我們可以一個1一個1的消去， 最后變成補集的一個子集。
但是必須當且僅當 至少有一個 a 等于 x 的時候， 可以直接dfs(all ^ x) ,否則直接消1連邊

AC代碼：

#include <bits/stdc++.h>using namespace std; const int maxn = 1<<22;int n, m, a[maxn], all; int vis[maxn]; int have[maxn];void dfs(int x) {if(vis[x]) return;vis[x] = 1;if(have[x]) dfs(all ^ x);for(int i = 0;i < n;i ++) {if(x & 1 << i) dfs(x ^ 1 << i);} } int main() {ios::sync_with_stdio(false), cin.tie(0);cin >> n >> m;for(int i = 1;i <= m;i ++) cin >> a[i];for(int i = 1;i <= m;i ++) have[a[i]] = 1;all = 1<<n;all--;int res = 0;for(int i = 1;i <= m;i ++) {if(!vis[a[i]]) {vis[a[i]] = 1;res ++;dfs(all ^ a[i]);}}cout << res << '\n';return 0; } 正確思路：
對于一個數 11000 則 他必定可以 與 00111相鏈接， 那么也一定可以和00111中間少了任何幾個1的數相連。

任何我們對于任意一個數都跑出他的父親， 他的父親就比他多一個1。

如 00001 他的父親可以為 10001 01001 00101 00011 這4個， 至于 10101 則是 10001（00101）的父親。

但是，對于一個數來說，他不能直接和他的父節點鏈接，必須要父節點先和別的數鏈接，然后子節點就一定可以和父節點鏈接的那個數鏈接。

我們先從小到大跑出所有的可以父節點，開另外一個數組去標記。

然后我們從大的數先開始處理，這樣我們就會先訪問到祖先節點，再訪問到子節點，這樣可以保證，我們訪問到子節點的時候，他的父節點已經處理過了，我們可以得知這2個點是否可以相連接。

對于處理到每一個點，我們先找他的所有父節點，如果可以鏈接，就直接鏈接，如果他不能和父節點鏈接，就去找他的對立節點（即0->1， 1->0），看看這2個點是否可以鏈接，可以就相連，不可以就將這個節點標記為-1，即沒有鏈接的節點，從而當該節點的子節點訪問的時候，就可以得知不能鏈接。

然后鏈接的時候用并查集鏈接塊，最后看有幾個聯通塊就是答案了。

#include<bits/stdc++.h> using namespace std; const int N = (1<<22) + 100; bool vis[N], vis1[N]; int pre[N]; int Find(int x){if(x == pre[x]) return x;return pre[x] = Find(pre[x]); } int main(){int n, m, t, to, u, v;scanf("%d%d", &n, &m);int Max = (1<<n) - 1;for(int i = 1; i <= m; i++){scanf("%d", &t);vis[t] = 1;}for(int i = 0; i <= Max; i++){vis1[i] |= vis[i];if(vis1[i]) {for(int j = 0; j < n; j++)vis1[i|(1<<j)] = 1;}}bool f = 0;for(int i = 0; i <= Max; i++) pre[i] = i;for(int i = Max; i >= 0; i--){if(!vis1[i]){pre[i] = -1;continue;}f = 0;for(int j = 0; j < n; j++){if(i&(1<<j)) continue;to = i|(1<<j);if(pre[to] != -1){u = Find(i);v = Find(to);pre[u] = v;f = 1;}}if(!f){to = Max ^ i;if(vis1[to]) {u = Find(i);v = Find(to);pre[u] = v;}else pre[i] = -1;}}int ans = 0;for(int i = 0; i <= Max; i++){if(vis[i] && pre[i] == -1) ans++;if(pre[i] == i) ans++;}printf("%d\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的Codeforces987F AND Graph的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。