並查集 並查集，在一些有N個元素的集合應用問題中，我們通常是在開始時讓每個元素構成一個單元素的集合，然後按一定順序將屬於同一組的元素所在的集合合併，其間要反覆查找一個元素在哪個集合中。這一類問題近幾年來反覆出現在信息學的國際國內賽題中，其特點是看似並不複雜，但數據量極大，若用正常的數據結構來描述的話 ...
並查集
並查集，在一些有N個元素的集合應用問題中，我們通常是在開始時讓每個元素構成一個單元素的集合，然後按一定順序將屬於同一組的元素所在的集合合併，其間要反覆查找一個元素在哪個集合中。這一類問題近幾年來反覆出現在信息學的國際國內賽題中，其特點是看似並不複雜，但數據量極大，若用正常的數據結構來描述的話，往往在空間上過大，電腦無法承受；即使在空間上勉強通過，運行的時間複雜度也極高，根本就不可能在比賽規定的運行時間（1～3秒）內計算出試題需要的結果，只能用並查集來描述。
並查集是一種樹型的數據結構，用於處理一些不相交集合的合併及查詢問題。常常在使用中以森林來表示。
例題：
輸入格式：
第一行包含兩個整數N、M，表示共有N個元素和M個操作。
接下來M行，每行包含三個整數Zi、Xi、Yi
當Zi=1時，將Xi與Yi所在的集合合併
當Zi=2時，輸出Xi與Yi是否在同一集合內，是的話輸出Y；否則話輸出N
輸出格式：
如上，對於每一個Zi=2的操作，都有一行輸出，每行包含一個大寫字母，為Y或者N
模版代碼：
#include<cstdio> #include<iostream> using namespace std; int a1,a2,a3,f[200001],n,m; int getf(int o) { if (f[o]==o) return o; else return f[o]=getf(f[o]); } void make(int v, int u) { int t1,t2; t1=getf(v); t2=getf(u); if (t1!=t2) f[t2]=t1; return; } void find(int v,int u) { int t1,t2; t1=getf(v); t2=getf(u); if (t1==t2) printf("Y\n"); else printf("N\n"); } int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) f[i]=i; for (int i=1; i<=m; i++) { scanf("%d%d%d", &a1, &a2, &a3); if (a1==1) make(a2, a3); else find(a2, a3); } return 0; }
主要應用類型：
1.團夥問題(搭橋問題，修路問題)：求連通塊
2.最小生成樹(kruskal)
3.L最近公共祖先(LCA)中的Tarjan
並查集的合併過程：(路徑壓縮)
int find(int x) { if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x]; //或 return x==fa[x] ? x : fa[x]=find(fa[x]); }
因此，並查集在查詢是否在同一集合時十分快捷
if(fa[a]==fa[b]) { ... }
與並查集相對的，可以有一種拆分集：
例題：
題目描述:
維護一個數據結構支持下列兩個操作：
-刪除某條邊，表示為”D x”，即為刪除第x條邊
-查詢兩點是否屬於一個集合，表示為”Q a b”，即為查詢節點a與節點b是否在一個集合內，若在同一個集合內，輸出”Yes”，否則輸出”No”（輸出不包括引號）
輸入:
第一行包括三個正整數數據結構中節點的個數n，邊數m，操作數q
接下來的m行每行包括兩個正整數u,v，表示節點u與節點v在同一個集合里
再接下來的q行每行包括一個格式如題描述操作
輸出:
對於每一個查詢，輸出包括一行，表示查詢結果，即如果兩點屬於同一個集合輸出”Yes”，否則輸出”No”。
實際上，將刪除操作存下來，反向就可以建立並查集，將答案倒序輸出即可
代碼：
#include<cstdio> #include<cstring> #include<iostream> #define CL(X,N) memset(X, N, sizeof(X)) #define LL long long using namespace std; const int maxn=1e5+10; int n, m, q; int a[maxn], b[maxn]; int u[maxn], v[maxn], f[maxn]; char op[maxn]; bool del_state[maxn]; int _find(int x) { return x==f[x] ? x : f[x]=_find(f[x]); } void merge(int x, int y) { f[_find(y)]=_find(x); return ; } int main() { scanf("%d%d%d", &n, &m, &q); for(int i=1; i<=n; i++) f[i]=i; for(int i=1; i<=m; i++) scanf("%d%d", a+i, b+i); for(int i=1; i<=q; i++) { char cmd[2]; scanf("%s", cmd); op[i]=cmd[0];/*存操作符*/ switch(cmd[0]) { case 'D' : { scanf("%d", u+i); del_state[u[i]]=1;/*是否刪除*/ break; } case 'Q' : { scanf("%d%d", u+i, v+i); break; } default : break; } } for(int i=1; i<=m; i++) if(!del_state[i]) merge(a[i], b[i]); /*將沒被刪除的邊加入集合*/ int ans[maxn], cnt=0; for(int i=q; i>0; i--) { if(op[i]=='Q') { if(_find(u[i])==_find(v[i])) ans[cnt++]=1; else ans[cnt++]=0;/*正向存答案*/ } else merge(a[u[i]], b[u[i]]); } for(int i=cnt-1; i>=0; i--) printf(ans[i] ? "Yes\n" : "No\n");/*倒序輸出答案*/ return 0; }
如果有多種歸屬的情況，可以考慮建立多倍並查集
例題：
洛谷上 Sooke (dalao)的講解很詳細，此處就不再多說(才不是我懶得寫了)這道題比較巧妙的地方在於判斷相關性，建議一做。
至於Tarjan，這個演算法主要還是與LCA有關，並查集只是中途用來判斷兩點是否在同一棵子樹，不過對並查集的利用還是很巧妙的
下麵給出部分Tarjan的模版代碼：
void work(int fa,int son) { //這裡是Tarjan部分 f[son]=son; for(int i=head[son];i;i=edge[i].net) { int to=edge[i].to; if(to==fa) continue; dis[to]=dis[son]+edge[i].c; /*更新深度*/ work(son,to); f[to]=son; } ...
return ; }
由於遞歸過程中，work(son, to) 比 f[to]=son先執行，因此可以看做這是在樹上自底向上將節點加入並查集
". . ." 部分可以是對深度或距離的更新查詢，但由於查詢順序不一定於答案順序相同(work(fa, son) 函數像先序遍歷)，就需要先存再輸出，不過整個演算法的時間複雜度是十分優秀的(因為只查詢了一遍)
對於答案順序的具體原因這裡不做更多說明，希望瞭解的還請瀏覽其他博客
(最後好像水了點)
