并查集由一個整數(shù)型的數(shù)組和兩個函數(shù)構成颈走。數(shù)組pre[]記錄了每個點的前導點是什么民轴，函數(shù)find是查找敞峭，join是合并踊谋。
int pre[1000 ];
//查找根節(jié)點
int find(int x){
//返回根節(jié)點 r
int r=x;
while ( pre[r ] != r )
r=pre[r ];
//路徑壓縮
int i=x , j ;
while( i != r ){
j = pre[ i ]; // 在改變上級之前用臨時變量 j 記錄下他的值
pre[ i ]= r ; //把上級改為根節(jié)點
i=j;
}
return r ;
}
//判斷x y是否連通
void join(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) //如果不連通，就把它們所在的連通分支合并起
pre[fx ]=fy;
//如果已經(jīng)連通旋讹，就不用管了
}
為了解釋并查集的原理殖蚕，我將舉一個更有愛的例子。 話說江湖上散落著各式各樣的大俠沉迹，有上千個之多睦疫。他們沒有什么正當職業(yè)，整天背著劍在外面走來走去鞭呕，碰到和自己不是一路人的蛤育，就免不了要打一架。但大俠們有一個優(yōu)點就是講義氣葫松，絕對不打自己的朋友瓦糕。而且他們信奉“朋友的朋友就是我的朋友”烟阐，只要是能通過朋友關系串聯(lián)起來的臣缀，不管拐了多少個彎，都認為是自己人醋虏。這樣一來党晋，江湖上就形成了一個一個的群落谭胚，通過兩兩之間的朋友關系串聯(lián)起來。而不在同一個群落的人未玻，無論如何都無法通過朋友關系連起來灾而，于是就可以放心往死了打。但是兩個原本互不相識的人扳剿，如何判斷是否屬于一個朋友圈呢旁趟？
但是還有問題啊耕餐，大俠們只知道自己直接的朋友是誰凡傅，很多人壓根就不認識隊長，要判斷自己的隊長是誰肠缔，只能漫無目的的通過朋友的朋友關系問下去：“你是不是隊長夏跷？你是不是隊長？”這樣一來明未，隊長面子上掛不住了槽华，而且效率太低，還有可能陷入無限循環(huán)中趟妥。于是隊長下令猫态，重新組隊。隊內所有人實行分等級制度煮纵，形成樹狀結構懂鸵，我隊長就是根節(jié)點，下面分別是二級隊員行疏、三級隊員匆光。每個人只要記住自己的上級是誰就行了。遇到判斷敵友的時候酿联，只要一層層向上問终息，直到最高層，就可以在短時間內確定隊長是誰了贞让。由于我們關心的只是兩個人之間是否連通周崭，至于他們是如何連通的，以及每個圈子內部的結構是怎樣的喳张，甚至隊長是誰续镇，并不重要。所以我們可以放任隊長隨意重新組隊销部，只要不搞錯敵友關系就好了摸航。于是，門派產(chǎn)生了舅桩。
我們可以在每個朋友圈內推舉出一個比較有名望的人，作為該圈子的代表人物庇绽，這樣锡搜，每個圈子就可以這樣命名“齊達內朋友之隊”“羅納爾多朋友之隊”……兩人只要互相對一下自己的隊長是不是同一個人橙困，就可以確定敵友關系了。
下面我們來看并查集的實現(xiàn)酱虎。 int pre[1000]; 這個數(shù)組，記錄了每個大俠的上級是誰擂涛。大俠們從1或者0開始編號（依據(jù)題意而定）读串，pre[15]=3就表示15號大俠的上級是3號大俠。如果一個人的上級就是他自己，那說明他就是掌門人了恢暖，查找到此為止排监。也有孤家寡人自成一派的，比如歐陽鋒杰捂，那么他的上級就是他自己社露。每個人都只認自己的上級。比如胡青牛同學只知道自己的上級是楊左使琼娘。張無忌是誰？不認識附鸽！要想知道自己的掌門是誰脱拼，只能一級級查上去。 find這個函數(shù)就是找掌門用的坷备，意義再清楚不過了（路徑壓縮算法先不論熄浓，后面再說）。
int find(int x) { //查找我（x）的掌門
int r=x; //委托 r 去找掌門
while (pre[r]!=r) //如果r的上級不是r自己（也就是說找到的大俠他不是掌門 ）
r=pre[r] ; // r 就接著找他的上級省撑，直到找到掌門為止赌蔑。
return r ; //掌門駕到
}
再來看看join函數(shù)，就是在兩個點之間連一條線竟秫，這樣一來娃惯，原先它們所在的兩個板塊的所有點就都可以互通了。這在圖上很好辦肥败，畫條線就行了趾浅。但我們現(xiàn)在是用并查集來描述武林中的狀況的，一共只有一個pre[]數(shù)組馒稍，該如何實現(xiàn)呢皿哨？ 還是舉江湖的例子，假設現(xiàn)在武林中的形勢如圖所示纽谒。虛竹小和尚與周芷若MM是我非常喜歡的兩個人物证膨，他們的終極boss分別是玄慈方丈和滅絕師太，那明顯就是兩個陣營了鼓黔。我不希望他們互相打架央勒，就對他倆說：“你們兩位拉拉勾，做好朋友吧请祖《┩幔”他們看在我的面子上，同意了肆捕。這一同意可非同小可刷晋，整個少林和峨眉派的人就不能打架了。這么重大的變化，可如何實現(xiàn)呀眼虱，要改動多少地方喻奥？其實非常簡單，我對玄慈方丈說：“大師捏悬，麻煩你把你的上級改為滅絕師太吧撞蚕。這樣一來，兩派原先的所有人員的終極boss都是師太过牙，那還打個球吧谩！反正我們關心的只是連通性寇钉，門派內部的結構不要緊的刀疙。”玄慈一聽肯定火大了：“我靠扫倡，憑什么是我變成她手下呀谦秧，怎么不反過來？我抗議撵溃！”抗議無效疚鲤，上天安排的，最大缘挑。反正誰加入誰效果是一樣的集歇，我就隨手指定了一個。這段函數(shù)的意思很明白了吧卖哎？
void join(int x,int y){ //我想讓虛竹和周芷若做朋友
int fx=find(x),fy=find(y); //虛竹的老大是玄慈鬼悠，芷若MM的老大是滅絕
if(fx!=fy) //玄慈和滅絕顯然不是同一個人
pre[fx ]=fy; //方丈只好委委屈屈地當了師太的手下啦
}
再來看看路徑壓縮算法。建立門派的過程是用join函數(shù)兩個人兩個人地連接起來的亏娜，誰當誰的手下完全隨機焕窝。最后的樹狀結構會變成什么胎唇樣，我也完全無法預計维贺，一字長蛇陣也有可能它掂。這樣查找的效率就會比較低下。最理想的情況就是所有人的直接上級都是掌門溯泣，一共就兩級結構虐秋，只要找一次就找到掌門了。哪怕不能完全做到垃沦，也最好盡量接近客给。這樣就產(chǎn)生了路徑壓縮算法。 設想這樣一個場景：兩個互不相識的大俠碰面了肢簿，想知道能不能揍靶剑。 于是趕緊打電話問自己的上級：“你是不是掌門蜻拨？” 上級說：“我不是呀，我的上級是誰誰誰桩引，你問問他看看缎讼。” 一路問下去坑匠，原來兩人的最終boss都是東廠曹公公血崭。 “哎呀呀，原來是記己人厘灼，西禮西禮夹纫，在下三營六組白面葫蘆娃!” “幸會幸會，在下九營十八組仙子狗尾巴花设凹！” 兩人高高興興地手拉手喝酒去了捷凄。 “等等等等，兩位同學請留步围来，還有事情沒完成呢！”我叫住他倆匈睁。 “哦监透，對了，還要做路徑壓縮航唆≌吐”兩人醒悟。 白面葫蘆娃打電話給他的上級六組長：“組長啊糯钙，我查過了粪狼，其習偶們的掌門是曹公公。不如偶們一起及接拜在曹公公手下吧任岸，省得級別太低再榄，以后查找掌門麻環(huán)∠砬保” “唔困鸥，有道理〗０矗” 白面葫蘆娃接著打電話給剛才拜訪過的三營長……仙子狗尾巴花也做了同樣的事情疾就。 這樣，查詢中所有涉及到的人物都聚集在曹公公的直接領導下艺蝴。每次查詢都做了優(yōu)化處理猬腰，所以整個門派樹的層數(shù)都會維持在比較低的水平上。路徑壓縮的代碼猜敢，看得懂很好姑荷，看不懂也沒關系盒延，直接抄上用就行了∠崾茫總之它所實現(xiàn)的功能就是這么個意思兰英。
