數據結構之並查集進階
來自專欄中國有演算法
7 人贊了文章
並查集並不是什麼比較複雜的演算法，可以輕鬆掌握。
並查集的基本操作也就是初始化，一個find函數找到根節點，一個join函數合併節點。下面給出這三個操作我自己的習慣寫法，就不再多做贅述了。
for(int i=1;i<=n;i++) f[i]=i;int find(int x){ return x==f[x]?x:f[x]=find(f[x]);}void join(int x,int y){ int fx=find(x),fy=find(y); if(fx!=fy) f[fx]=fy; }
這裡我們主要討論並查集的進階用法。
next數組優化時間
在有的關於並查集的題目中，可能會被故意卡你的時間點，這種情況就很容易會TLE。這時就需要優化一下時間，next數組就是用來優化時間的。
最普通的就是給你一個區間，讓你把區內所有的點全部連起來，這時候就可以考慮next數組優化了。
例題：http://codeforces.com/problemset/problem/566/D
next數組優化的模板如下：
for(int i=1;i<=n;i++){ f[i]=i; next[i]=i+1;//初始化使next[i]指向下一個}for(int i=x;i<y;i=temp){ join(i,y); temp=next[i]; next[i]=y+1;//當再次循環到該區間時，直接跳到區間下一個 }
例題的AC代碼如下：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=2e5+10; int n,q,f[N],next[N];int find(int x){ return x==f[x]?x:f[x]=find(f[x]);}void join(int x,int y){ int fx=find(x),fy=find(y); if(fx!=fy) f[fx]=fy; }int main(){ while(~scanf("%d%d",&n,&q)){ for(int i=1;i<=n;i++){ f[i]=i; next[i]=i+1;//初始化使next[i]指向下一個 }// for(int i=x;i<y;i=temp){// join(i,y);// temp=next[i];// next[i]=y+1;//當再次循環到該區間時，直接跳到區間下一個 // } int t,x,y; while(q--){ scanf("%d%d%d",&t,&x,&y); if(t==1){ join(x,y); }else if(t==2){ int temp; for(int i=x;i<y;i=temp){ join(i,y); temp=next[i]; next[i]=y+1;//當再次循環到該區間時，直接跳到區間下一個 } }else{ int fx=find(x),fy=find(y); if(fx==fy) printf("YES
"); else printf("NO
"); } } } return 0;}
種類並查集
其實所謂的種類並查集就是帶關係的並查集，當子節點與其父節點相連時，兩者並不止存在「父子關係」還存在一種依賴於父子關係的附加關係，題目會要求你通過該關係求出一個結果。
例題：http://poj.org/problem?id=1703
此關係大多可以通過「父子三代」的關係映射得出，用w數組記錄（我習慣用w代表額外的關係），w代表了當前節點與其父節點的關係。
種類並查集的基本操作與傳統並查集並無太大區別，只要在初始化、查找、合併，這三個操作中，依據附加關係加入對w數組的操作即可。下面我們來詳細分析這三步中對w的相應操作。
初始化：
對當前的初始狀態的各個節點分析其初始狀態對應的狀態數。
for(int i=1;i<=n;i++){ f[i]=i; w[i]=1;}
對該例題而言，我們設0代表當前節點與其父節點分屬不同的團伙，1代表兩者來自同一團體，初始化的時候，每個節點的根節點都來自自己，而自己與自己當然是屬於同一團伙，所以全部初始化為1。
查找：
普通的查找操作實際就是通過遞歸找到該子樹的根節點，而且為了減少下次的搜索時間我們習慣於用路徑壓縮的方法來優化時間，所以我們本質上分析的其實是當前節點與其根節點的關係，這可以從搜到的根節點倒著回溯。
因為回溯過程中會壓縮路徑，所以我們可以把每個當前節點看作根節點的「孫節點」，即根節點的子節點的子節點。所以對每個當前節點與其根節點的關係，我們可以從當前節點與其父節點的關係和其父節點與其根節點的關係得出。也就是我上文所說的「父子三代」的關係映射。
int find(int x){ if(f[x]==x) return x; int temp = f[x]; f[x] =find(f[x]); w[x] = cal_1(w[x],w[temp]) ; return f[x];}
這裡的cal_1(w[x],w[temp])即代表「父子三代」的關係運算，在這裡運算時我們可以把三種關係的所有狀態都列出來，然後找規律，用w[x]和w[f[x]]推出x與其根節點的關係。
/* w[x] cal1(w[x], w[temp]) 1 1 1 1 0 0 0 0 1 0 1 0 。 f[f[x]] | | w[temp] 1 0 0 | 。 f[x] | | w[x] 1 0 1 | 。 x //例題關係圖 //我們可以得出該關係為 w[x]=(w[x]+w[temp]+1)%2;*/
PS：這裡要注意的一點是我們必須在其搜到根節點之後再開始更新w數組，因為我們要藉助是在回溯過程中計算關係，還有因為在搜到根節點之前，我們還必須保存當前節點與父節點的關係，所以我們設了一個臨時變數temp來保存f[x]的值（一開的時候這沒搞清楚wa了幾發~）
合併：
如果說查找是對「父子三代」的關係計算，那麼合併操作就是對雙方及其父節點的關係運算。因為我們再上一步中經每個節點都連在了跟根節點上，所以我們在普通的合併操作的節點查詢的時候對查詢的兩個節點會向上查詢他的根節點，而其父節點就是其根節點。所以當兩個節點屬於不同子樹的時候，對兩者根節點的操作就轉化為了對其父節點的操作。
與上述的查詢操作類似，我們要求的兩者父節點的關係可以通過當前兩個節點的關係及其兩者與各自父節點的關係推出。也就是通過三個關係求一個關係，我們也可以將所有的關係狀態一一列出，從中歸納出關係式。
void join(int x,int y){ int fx=find(x),fy=find(y); if(fx!=fy) { f[fx]=fy; w[fx]=cal_2(w[x],w[y]); }}
從表達式 cal_2(w[x],w[y]); 可以看出我們要求的w[fx]是通過w[x]與w[y]的狀態得出來的，但實際上我們還包含有一個隱含關係，就是x與y的關係。
/* w[fx]=cal_2( w[x], w[y]); 0 1 1 0 0 0 1 1 0 w[f[x]] 。f[x]————————> 。f[y] | | | w[x] | w[y] | 1 | 1 | 0 | 0 | 1 | 0 。x—————————> 。 y //例題關係圖 //我們可以得出該關係為w[fx]=(w[x]+w[y])%2; */
種類並查集的三個操作的模板已經全部給出，只要對此類型的題目套模板就行了，比較困難的也就只有兩個表達式的推理，但我們如果實在推不出來，而且狀態量不算太多，可以用一種比較耍賴的方法暴力求出，即使用if-else大法，暴力枚舉出所有狀態量。
下面給出例題的AC代碼：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=1e5+10;int t,n,m,f[N],w[N];int find(int x){ if(x==f[x]) return x; int temp=f[x]; f[x]=find(f[x]); w[x]=(w[x]+w[temp]+1)%2; return f[x];}void join(int x,int y){ int fx=find(x),fy=find(y); if(fx!=fy){ f[fx]=fy; w[fx]=(w[x]+w[y])%2; }}int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ f[i]=i; w[i]=1; } char c;int a,b; while(m--){ scanf(" %c%d%d",&c,&a,&b); if(c==D) join(a,b); else{ if(find(a)!=find(b)) printf("Not sure yet.
"); else if((w[a]+w[b])%2) printf("In different gangs.
"); else printf("In the same gang.
");// if(find(a)==find(b) && w[a]==w[b])// printf("In the same gang.
");// else if(find(a)==find(b) && w[a]!=w[b])// printf("In different gangs.
");// else // printf("Not sure yet.
"); } } } return 0;}
--------------------------------------------結語----------------------------------------------
至此，對與並查集的進階操作就完成了，其實就並查集而言，只是我們演算法學習中很簡單的一部分，我們花了很多的篇幅來描述該演算法，主要是為了讓我們能更容易理解。
好了終於結束了~
期待下一節的演算法吧。
推薦閱讀：