題干：

小T有n個點，每個點可能是黑色的，可能是白色的。
小T對這張圖的定義了白連通塊和黑連通塊：
白連通塊：圖中一個點集V，若滿足所有點都是白點，并且V中任意兩點都可以只經過V中的點互相到達，則稱V中的點構成了一個白連通塊。

黑連通塊：類似白連通塊的定義。

小T對這n個點m次操作。
1、在兩個點之間連一條邊。
2、詢問白（黑）連通塊個數。
3、給出x,y兩個點，保證同色（為了方便描述，x,y都是白點，黑色同理）。詢問存在多少個黑點，將它改變顏色后，x,y所在的白連通塊會合并為一個。如果x,y已經在一個白連通塊內了，輸出-1。（注意：這里不會對點的顏色改變，只統計個數）

?

?

輸入描述:

第一行兩個整數n,m，分別表示點的個數和操作的個數。 第二行n個整數，第i個整數描述第i個點的顏色，0表示白色，1表示黑色。 接下來m行，每行包含2個或者3個整數，描述三種操作。 操作1：1,x,y，表示在x,y之間加入一條邊。 操作2：2,x，若x=0，詢問白連通塊的個數，否則詢問黑連通塊的個數。 操作3：3,x,y，表示第三種操作。 n,m≤50000,x,y≤nn,m≤50000,x,y≤n

輸出描述:

對于詢問操作，輸出一個整數。

示例1

輸入

復制

6 7 0 1 0 0 0 1 1 3 2 1 2 4 3 3 4 1 1 3 2 0 3 1 4 3 1 3

輸出

復制

1 3 1 -1

說明

第一次詢問：2號點變成白色后，3,4所在的白連通塊合并為一個。 第二次詢問：白連通塊的個數為3，分別是{1,2}，{3}，{4}。 第三次詢問：2號點變成白色后，1,4所在的白連通塊合并為一個。 第四次詢問：1,3已經是同一個白連通塊了，輸出-1。

解題報告：

并查集+bitset優化。
操作二可以在加邊的過程中求出。即加入一條端點同色的邊，并查集判斷是否可以消去一個白（黑）連通塊。
操作三求的是x,y所在的兩個白連通塊都連出的黑點（假設x,y是白色，黑色的情況是一樣的）。
于是可以bitset維護每個白聯通塊連出的黑點，黑連通塊連出的白點。每加入一條端點異色的邊，在兩個白、黑連通塊的bitset中將一個位置設為1；加入一條端點同色的邊，就是合并白（黑）連通塊的過程，同時合并兩個白（黑）連通塊的bitset。
復雜度，W=32或64

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<bitset> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 6e4 + 5; int col[MAX]; int f[MAX]; int totbai,tothei,bai,hei; bitset<MAX> bs[MAX]; int getf(int v) {return v == f[v] ? v : f[v] = getf(f[v]); } void add(int u,int v) {int t1 = getf(u);int t2 = getf(v);if(col[u] == col[v]) {if(t1 != t2) {if(col[u] == 0) bai--;else hei--; }f[t2] = t1;bs[t1] |= bs[t2];//這兩句也可以放在if里 }else {bs[t1].set(v);//bs[t1][v]=1;bs[t2].set(u);//bs[t2][u]=1;} } int main() {int n,m;cin>>n>>m;for(int i = 1; i<=n; i++) {scanf("%d",col+i);f[i] = i;}for(int i = 1; i<=n; i++) {if(col[i] == 1) hei++,tothei++;else bai++,totbai++;}for(int op,x,y,i = 1; i<=m; i++) {scanf("%d",&op);if(op == 1) {scanf("%d%d",&x,&y);add(x,y);}else if(op == 2) {scanf("%d",&x);printf("%d\n",x == 1 ? hei : bai);}else {scanf("%d%d",&x,&y);int t1 = getf(x);int t2 = getf(y);if(t1 == t2) puts("-1");else {printf("%d\n",(bs[t1]&bs[t2]).count());}}}return 0 ;}

其實merge函數這樣寫比較清晰：

void merge(int u,int v) {int t1 = getf(u),t2 = getf(v);if(t1 == t2) return;if(col[t1] == col[t2]) { if(col[t1] == 1) hei--;else bai--;f[t2]=t1;bs[t1] |= bs[t2];}else bs[t1][v]=bs[t2][u]=1; }

?

簡化版：

const int N=5e4+5; int n,m,col[N],fa[N],num[2];bitset<N>S[N]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} int main(){n=gi();m=gi();for(int i=1;i<=n;++i)++num[col[i]=gi()],fa[i]=i;while(m--){int op=gi(),x=gi(),y;if(op&1)y=gi();if(op==1)if(col[x]^col[y])S[find(x)][y]=1,S[find(y)][x]=1;else{x=find(x),y=find(y);if(x^y)fa[y]=x,S[x]|=S[y],--num[col[x]];}if(op==2)printf("%d\n",x?num[1]:num[0]);if(op==3)printf("%d\n",find(x)^find(y)?(int)(S[find(x)]&S[find(y)]).count():-1);}return 0; }

總結：

? 這個tothei和totbai，計算過程中始終沒有用到，但是作為一個流程性的東西，萬一給你改變一下題目，說不定就用到了，所以提前維護出來為好。?

總結

以上是生活随笔為你收集整理的【牛客 - 368D】动态连通块（并查集+bitset优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

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