查并集是一個(gè)很重要的數(shù)據(jù)結(jié)構(gòu)，特別適合解決一些類(lèi)似于圖，集合的問(wèn)題。比如這個(gè)：http://acm.hdu.edu.cn/showproblem.php?pid=1232
什么是并查集？
為了解釋并查集的原理，我將舉一個(gè)更有愛(ài)的例子。 話(huà)說(shuō)江湖上散落著各式各樣的大俠，有上千個(gè)之多。他們沒(méi)有什么正當(dāng)職業(yè)，整天背著劍在外面走來(lái)走去，碰到和自己不是一路人的，就免不了要打一架。但大俠們有一個(gè)優(yōu)點(diǎn)就是講義氣，絕對(duì)不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”，只要是能通過(guò)朋友關(guān)系串聯(lián)起來(lái)的，不管拐了多少個(gè)彎，都認(rèn)為是自己人。這樣一來(lái)，江湖上就形成了一個(gè)一個(gè)的群落，通過(guò)兩兩之間的朋友關(guān)系串聯(lián)起來(lái)。而不在同一個(gè)群落的人，無(wú)論如何都無(wú)法通過(guò)朋友關(guān)系連起來(lái)，于是就可以放心往死了打。但是兩個(gè)原本互不相識(shí)的人，如何判斷是否屬于一個(gè)朋友圈呢？
我們可以在每個(gè)朋友圈內(nèi)推舉出一個(gè)比較有名望的人，作為該圈子的代表人物，這樣，每個(gè)圈子就可以這樣命名“齊達(dá)內(nèi)朋友之隊(duì)”“羅納爾多朋友之隊(duì)”……兩人只要互相對(duì)一下自己的隊(duì)長(zhǎng)是不是同一個(gè)人，就可以確定敵友關(guān)系了。
但是還有問(wèn)題啊，大俠們只知道自己直接的朋友是誰(shuí)，很多人壓根就不認(rèn)識(shí)隊(duì)長(zhǎng)，要判斷自己的隊(duì)長(zhǎng)是誰(shuí)，只能漫無(wú)目的的通過(guò)朋友的朋友關(guān)系問(wèn)下去：“你是不是隊(duì)長(zhǎng)？你是不是隊(duì)長(zhǎng)？”這樣一來(lái)，隊(duì)長(zhǎng)面子上掛不住了，而且效率太低，還有可能陷入無(wú)限循環(huán)中。于是隊(duì)長(zhǎng)下令，重新組隊(duì)。隊(duì)內(nèi)所有人實(shí)行分等級(jí)制度，形成樹(shù)狀結(jié)構(gòu)，我隊(duì)長(zhǎng)就是根節(jié)點(diǎn)，下面分別是二級(jí)隊(duì)員、三級(jí)隊(duì)員。每個(gè)人只要記住自己的上級(jí)是誰(shuí)就行了。遇到判斷敵友的時(shí)候，只要一層層向上問(wèn)，直到最高層，就可以在短時(shí)間內(nèi)確定隊(duì)長(zhǎng)是誰(shuí)了。由于我們關(guān)心的只是兩個(gè)人之間是否連通，至于他們是如何連通的，以及每個(gè)圈子內(nèi)部的結(jié)構(gòu)是怎樣的，甚至隊(duì)長(zhǎng)是誰(shuí)，并不重要。所以我們可以放任隊(duì)長(zhǎng)隨意重新組隊(duì)，只要不搞錯(cuò)敵友關(guān)系就好了。于是，門(mén)派產(chǎn)生了。
并查集的優(yōu)化:路徑壓縮
這樣可以將查詢(xún)一個(gè)結(jié)點(diǎn)的根節(jié)點(diǎn)的時(shí)間復(fù)雜度降到O(1)。
實(shí)現(xiàn)
#include <iostream>
using namespace std;
//查找根節(jié)點(diǎn)
int find(int * pre,int length,int v){
int _v=v;
int root;
if(pre[_v]==_v){
return v;
}
while(pre[_v]!=_v){
_v=pre[_v];
}
root=_v;
//順便完成路徑壓縮
_v=v;
while(pre[_v]!=_v){
int temp=pre[_v]; // 在改變上級(jí)之前用臨時(shí)變量 j 記錄下他的值
pre[_v]=root;//把上級(jí)改為根節(jié)點(diǎn)
_v=temp;
}
return root; //返回根節(jié)點(diǎn) r
}
//判斷v1 v2是否連通
//如果已經(jīng)連通，就不用管了,如果不連通，就把它們所在的連通分支合并起,將v2合并到v1里面
void join(int * pre,int length,int v1,int v2){
int root_v1=find(pre,length,v1);
int root_v2=find(pre,length,v2);
if(root_v1==root_v2){
return ;
}else{
pre[v2]=root_v1;
}
}
void print(int * pre,int length){
for(int i=1;i<length;i++){
cout<<pre[i]<<" ";
}
cout<<endl;
}
int main(){
const int vertex=4;
const int n=vertex+1;
int pre[n];
//初始化
for(int i=1;i<n;i++){
pre[i]=i;
}
print(pre,n);
join(pre,n,1,2);
join(pre,n,3,4);
print(pre,n);
//判斷有幾個(gè)根節(jié)點(diǎn)
int arr_root[n];
//初始化為0
for(int i=0;i<n;i++){
arr_root[i]=0;
}
//將是根節(jié)點(diǎn)的點(diǎn)置為1
for(int i=1;i<n;i++){
arr_root[find(pre,n,i)]=1;
}
//統(tǒng)計(jì)一下置為1的結(jié)點(diǎn)的個(gè)數(shù)
int ans=0;
for(int i=1;i<n;i++){
if(arr_root[i]==1){
ans++;
}
}
cout<<ans<<endl;
system("pause");
return 0;
}
關(guān)于數(shù)據(jù)結(jié)合和算法的其他文章：
這又是一個(gè)flag http://m.itdecent.cn/p/1dc543da3897
update：
在論壇上面看見(jiàn)的一個(gè)問(wèn)題，用并查的思想可以很快的算出來(lái)。
