這篇博客是轉(zhuǎn)載來自一位大神，用武俠小說元素去介紹并查集的知識，關(guān)于那位大神簡單有趣感興趣的點這里

為了解釋并查集的原理，我將舉一個更有愛的例子。

話說江湖上散落著各式各樣的大俠，有上千個之多。他們沒有什么正當(dāng)職業(yè)，整天背著劍在外面走來走去，碰到和自己不是一路人的，就免不了要打一架。但大俠們有一個優(yōu)點就是講義氣，絕對不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”，只要是能通過朋友關(guān)系串聯(lián)起來的，不管拐了多少個彎，都認(rèn)為是自己人。這樣一來，江湖上就形成了一個一個的幫派，通過兩兩之間的朋友關(guān)系串聯(lián)起來。而不在同一個幫派的人，無論如何都無法通過朋友關(guān)系連起來，于是就可以放心往死了打。但是兩個原本互不相識的人，如何判斷是否屬于一個朋友圈呢？

我們可以在每個朋友圈內(nèi)推舉出一個比較有名望的人，作為該圈子的代表人物。這樣，每個圈子就可以這樣命名“中國同胞隊”美國同胞隊”……兩人只要互相對一下自己的隊長是不是同一個人，就可以確定敵友關(guān)系了。

但是還有問題啊，大俠們只知道自己直接的朋友是誰，很多人壓根就不認(rèn)識隊長要判斷自己的隊長是誰，只能漫無目的的通過朋友的朋友關(guān)系問下去：“你是不是隊長？你是不是隊長？”這樣，想打一架得先問個幾十年，餓都餓死了，受不了。這樣一來，隊長面子上也掛不住了，不僅效率太低，還有可能陷入無限循環(huán)中。于是隊長下令，重新組隊。隊內(nèi)所有人實行分等級制度，形成樹狀結(jié)構(gòu)，我隊長就是根節(jié)點，下面分別是二級隊員、三級隊員。每個人只要記住自己的上級是誰就行了。遇到判斷敵友的時候，只要一層層向上問，直到最高層，就可以在短時間內(nèi)確定隊長是誰了。由于我們關(guān)心的只是兩個人之間是否是一個幫派的，至于他們是如何通過朋友關(guān)系相關(guān)聯(lián)的，以及每個圈子內(nèi)部的結(jié)構(gòu)是怎樣的，甚至隊長是誰，都不重要了。所以我們可以放任隊長隨意重新組隊，只要不搞錯敵友關(guān)系就好了。于是，門派產(chǎn)生了。

下面我們來看并查集的實現(xiàn)。 int pre[1000]; 這個數(shù)組，記錄了每個大俠的上級是誰。大俠們從1或者0開始編號（依據(jù)題意而定），pre[15]=3就表示15號大俠的上級是3號大俠。如果一個人的上級就是他自己，那說明他就是掌門人了，查找到此為止。也有孤家寡人自成一派的，比如歐陽鋒，那么他的上級就是他自己。每個人都只認(rèn)自己的上級。比如胡青牛同學(xué)只知道自己的上級是楊左使。張無忌是誰？不認(rèn)識！要想知道自己的掌門是誰，只能一級級查上去。

find這個函數(shù)就是找掌門用的，意義再清楚不過了（路徑壓縮算法先不論，后面再說）。

int unionsearch(int root) //查找根結(jié)點 {int son, tmp;son = root;while(root != pre[root]) //我的上級不是掌門root = pre[root];while(son != root) //我就找他的上級，直到掌門出現(xiàn){tmp = pre[son];pre[son] = root;son = tmp;}return root; //掌門駕到~~ }

再來看看join函數(shù)，就是在兩個點之間連一條線，這樣一來，原先它們所在的兩個板塊的所有點就都可以互通了。這在圖上很好辦，畫條線就行了。但我們現(xiàn)在是用并查集來描述武林中的狀況的，一共只有一個pre[]數(shù)組，該如何實現(xiàn)呢？ 還是舉江湖的例子，假設(shè)現(xiàn)在武林中的形勢如圖所示。虛竹帥鍋與周芷若MM是我非常喜歡的兩個人物，他們的終極boss分別是玄慈方丈和滅絕師太，那明顯就是兩個陣營了。我不希望他們互相打架，就對他倆說：“你們兩位拉拉勾，做好朋友吧。”他們看在我的面子上，同意了。這一同意可非同小可，整個少林和峨眉派的人就不能打架了。這么重大的變化，可如何實現(xiàn)呀，要改動多少地方？其實非常簡單，我對玄慈方丈說：“大師，麻煩你把你的上級改為滅絕師太吧。這樣一來，兩派原先的所有人員的終極boss都是師太，那還打個球啊！反正我們關(guān)心的只是連通性，門派內(nèi)部的結(jié)構(gòu)不要緊的。”玄慈一聽肯定火大了：“我靠，憑什么是我變成她手下呀，怎么不反過來？我抗議！”于是，兩人相約一戰(zhàn)，殺的是天昏地暗，風(fēng)云為之變色啊，但是啊，這場戰(zhàn)爭終究會有勝負(fù)，勝者為王。弱者就被吞并了。反正誰加入誰效果是一樣的，門派就由兩個變成一個了。這段函數(shù)的意思明白了吧？

void join(int root1, int root2) //虛竹和周芷若做朋友 {int x, y;x = unionsearch(root1);//我老大是玄慈y = unionsearch(root2);//我老大是滅絕if(x != y) pre[x] = y; //打一仗，誰贏就當(dāng)對方老大 }

再來看看路徑壓縮算法。建立門派的過程是用join函數(shù)兩個人兩個人地連接起來的，誰當(dāng)誰的手下完全隨機。最后的樹狀結(jié)構(gòu)會變成什么樣，我也無法預(yù)知，一字長蛇陣也有可能。這樣查找的效率就會比較低下。最理想的情況就是所有人的直接上級都是掌門，一共就兩級結(jié)構(gòu)，只要找一次就找到掌門了。哪怕不能完全做到，也最好盡量接近。這樣就產(chǎn)生了路徑壓縮算法。

設(shè)想這樣一個場景：兩個互不相識的大俠碰面了，想知道能不能干一場。 于是趕緊打電話問自己的上級：“你是不是掌門？” 上級說：“我不是呀，我的上級是誰誰誰，你問問他看看。” 一路問下去，原來兩人的最終boss都是東廠曹公公。 “哎呀呀，原來是自己人，有禮有禮，在下三營六組白面葫蘆娃!” “幸會幸會，在下九營十八組仙子狗尾巴花！” 兩人高高興興地手拉手喝酒去了。 “等等等等，兩位大俠請留步，還有事情沒完成呢！”我叫住他倆。 “哦，對了，還要做路徑壓縮。”兩人醒悟。 白面葫蘆娃打電話給他的上級六組長：“組長啊，我查過了，其實偶們的掌門是曹公公。不如偶們一起結(jié)拜在曹公公手下吧，省得級別太低，以后查找掌門麻煩。” “唔，有道理。” 白面葫蘆娃接著打電話給剛才拜訪過的三營長……仙子狗尾巴花也做了同樣的事情。 這樣，查詢中所有涉及到的人物都聚集在曹公公的直接領(lǐng)導(dǎo)下。每次查詢都做了優(yōu)化處理，所以整個門派樹的層數(shù)都會維持在比較低的水平上。路徑壓縮的代碼，看得懂很好，看不懂可以自己模擬一下，很簡單的一個遞歸而已。總之它所實現(xiàn)的功能就是這么個意思。

于是，問題圓滿解決。。。。。。。。。

代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int pre[1010]; //里面全是掌門int unionsearch(int root) {int son, tmp;son = root;while(root != pre[root]) //尋找掌門ing……root = pre[root];while(son != root) //路徑壓縮{tmp = pre[son];pre[son] = root;son = tmp;}return root; //掌門駕到~ }int main() {int num, road, total, i, start, end, root1, root2;while(scanf("%d%d", &num, &road) && num){total = num - 1; //共num-1個門派for(i = 1; i <= num; ++i) //每條路都是掌門pre[i] = i;while(road--){scanf("%d%d", &start, &end); //他倆要結(jié)拜root1 = unionsearch(start);root2 = unionsearch(end);if(root1 != root2) //掌門不同？踢館！~{pre[root1] = root2;total--; //門派少一個，敵人（要建的路）就少一個}}printf("%d\n", total);//天下局勢：還剩幾個門派}return 0; }

例子就是杭電上的暢通工程：
http://acm.hdu.edu.cn/showproblem.php?pid=1232

首先在地圖上給你若干個城鎮(zhèn)，這些城鎮(zhèn)都可以看作點，然后告訴你哪些對城鎮(zhèn)之間是有道路直接相連的。最后要解決的是整幅圖的連通性問題。比如隨意給你兩個點，讓你判斷它們是否連通，或者問你整幅圖一共有幾個連通分支，也就是被分成了幾個互相獨立的塊。像暢通工程這題，問還需要修幾條路，實質(zhì)就是求有幾個連通分支。

如果是1個連通分支，說明整幅圖上的點都連起來了，不用再修路了；如果是2個連通分支，則只要再修1條路，從兩個分支中各選一個點，把它們連起來，那么所有的點都是連起來的了；如果是3個連通分支，則只要再修兩條路……
以下面這組數(shù)據(jù)輸入數(shù)據(jù)來說明
4 2 1 3 4 3
第一行告訴你，一共有4個點，2條路。下面兩行告訴你，1、3之間有條路，4、3之間有條路。那么整幅圖就被分成了1-3-4和2兩部分。只要再加一條路，把2和其他任意一個點連起來，暢通工程就實現(xiàn)了，那么這個這組數(shù)據(jù)的輸出結(jié)果就是1。好了，現(xiàn)在編程實現(xiàn)這個功能吧，城鎮(zhèn)有幾百個，路有不知道多少條，而且可能有回路。 這可如何是好？
我以前也不會呀，自從用了并查集之后，嗨，效果還真好！我們?nèi)叶加盟?#xff01;
并查集由一個整數(shù)型的數(shù)組和兩個函數(shù)構(gòu)成。數(shù)組pre[]記錄了每個點的前導(dǎo)點是什么，函數(shù)find是查找，join是合并。

int pre[1010]; //存放第i個元素的父節(jié)點int unionsearch(int root) //查找根結(jié)點 {int son, tmp;son = root;while(root != pre[root]) //尋找根結(jié)點root = pre[root];while(son != root) //路徑壓縮{tmp = pre[son];pre[son] = root;son = tmp;}return root; }void join(int root1, int root2) //判斷是否連通，不連通就合并 {int x, y;x = unionsearch(root1);y = unionsearch(root2);if(x != y) //如果不連通，就把它們所在的連通分支合并pre[x] = y; }

總結(jié)

以上是生活随笔為你收集整理的给并查集融入武侠元素——看完故事就会了的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。