什么是 “并查集” ？
導(dǎo)語：并查集是一種精巧的算法，本身并不難理解，卻很常用，在許多場景下都能找到并查集的身影。
本文作者封承成，年僅12歲，非常感謝他的投稿。
并查集是什么
并查集，是一種判斷“遠房親戚”的算法。
打個比方：你身邊的某個“朋友”，很有可能就是你父親的母親的姑媽的大姨的哥哥的表妹的孫子的女兒的父親的孫子。如果給定這么一張“家譜”（無向圖），如何判斷兩個頂點是不是“親戚”呢？用人話說，就是判斷一個圖中兩個點是否聯(lián)通（兩個頂點相互聯(lián)通則為親戚）。
并查集是專門用來解決這樣的問題的，和搜索不同，并查集在構(gòu)建圖的時候同時就標記出了哪個“人”屬于哪個“團伙”（一團伙中的點兩兩聯(lián)通）。
并查集的操作
1. 初始化
并查集的思想是通過標記確定該頂點所在的組。
所以對于一個n個點，m條邊的圖，我們需要新建一個長度為n的數(shù)組f（可以理解為father），f[n]代表點n的團伙“代表人”，當兩個點所在團伙“代表人”相同，則這兩個點所在團伙相同。
而在最開始，每個頂點間都是互相不連通的，所以每個頂點單獨屬于一個團伙，每個頂點理所應(yīng)當成為自己團伙的“代表人”，所以我們把f[n]的初始值賦為n。
2. 合并團伙
我們以連接3和1這兩個點做例子：
在連接點3和點1時，3和1形成了一個團伙，而3和1的團伙代表人f[3]和f[1]就應(yīng)該統(tǒng)一，具體是讓3做代表人還是讓1做代表人隨便，我們讓1做代表人。f[3] = 1，這條語句可以理解為讓1所在團伙的代表人同時成為3所在團伙的代表人。
（箭頭只是體現(xiàn)了f數(shù)組中“團伙成員”和“代表人”的關(guān)系，其實這個圖是無向圖）
可是，像f[a] = b這樣合并真的對嗎？請讀者考慮這樣一種情況。
剛剛我們合并了3和1，現(xiàn)在我們需要合并3和2。如果按照f[a] = b這樣合并，那么，f[3]就被賦值為了2。這樣，f[3]原本的值1就被覆蓋了，也就是說，1和3的團伙就被硬生生地“拆散”了。
下面我們換一個例子：合并3和4。此時我們不應(yīng)該令f[3] =4，應(yīng)該讓f[3的團伙代表人] = (4的團伙代表人)，如下圖。
這樣，合并兩個團伙的工作就完成了?？偨Y(jié)起來就一句話：f[a的團伙代表人] = (b的團伙代表人)。
3. 查找團伙代表人
緊接著，又一個問題浮出水面：根據(jù)上面的公式f[a的團伙代表人] = (b的團伙代表人)，可是a、b的團伙代表人怎么求？是f[a]嗎？不不不，這里的情況變得復(fù)雜了。大家再次考慮一種特殊情況。
在這種情況下，3的團伙代表人是誰？1還是4？正確答案是4。因為，一個團伙中每一個點都直接或間接地“指向”這個團伙的代表人。（1,3,4）這個團伙中，1直接地指向4，3間接地指向4，所以4才是這個團伙里的代表人。
那么，點x的團伙代表人怎么求呢？我們會發(fā)現(xiàn)另一個特征，任何一個團伙的代表人a，都有f[a] = a。很好理解，團伙代表人也是團伙的一個成員，團伙代表人所在團伙的代表人就是它自己。
而對于其他點a，f[a]均不等于a。并且如果一個頂點a有f[a] ≠ a，那么這個點一定不是團伙的代表人，因為f[a]不會間接地或直接地指向a（并查集保證不會存在環(huán)）。
根據(jù)這一特性，我們可以判斷點a是否為某個團伙的代表人。
在例子中，我們想要知道1是否為團伙代表人，就可以看f[1]是否等于1，很明顯，f[1] = 4，所以1不是該團伙的代表人，我們要繼續(xù)“追本溯源”，對5進行判斷。這個過程就是一種遞歸的尋找過程。
知道了這個特性，我們就可以寫出相應(yīng)的C++代碼（這里還給出了循環(huán)版的代碼，根據(jù)情況使用）：
int?getFather(int?x)?{
????return?f[x]?==?x???x?:?getFather(f[x]);
}
int?getFather(int?x)?{
????while?(f[x]?!=?x)
????????x?=?f[x];
????return?x;
}
這是一個遞歸函數(shù)，如果f[x] = x，說明這個點已經(jīng)是該團伙的代表人，直接返回就好了，如果它不是該團伙的代表人，那么就返回自己指向的點的團伙代表人。
在求getFather(3)時，f[3] != 3，返回getFather(f[3])也就是getFather(1)；
在求getFather(1)時，f[1] != 1，返回getFather(f[1])也就是getFather(4)；
在求getFather(4)時，f[4] == 4，返回4。遞歸結(jié)束。最后計算出3的團伙代表人是4。
4. 查詢頂點是否在同一團伙
并查集的最后一種操作叫做查詢，就是查詢兩個點是否連通（在同一團伙）。
前面已經(jīng)講了，當兩個點所在團伙“代表人”相同，則這兩個點所在團伙相同。判斷兩個點a、b在同一團伙的方法就是：
getFather(a)?==?getFather(b)?
5. 完整代碼
const?int?N?=?100;?//?節(jié)點數(shù)量
int?f[N];
int?init()?{
????//?初始化
????for?(int?i=0;?i????????f[i]?=?i;
}
int?getFather(int?x)?{
????//?查詢所在團伙代表人
????return?f[x]==x???x?:?getFather(f[x]);
}
int?merge(int?a,?int?b)?{
????//?合并操作
????f[getFather(a)]?=?getFather(b);
}
bool?query(int?a,?int?b)?{
????//?查詢操作
????return?getFather(a)?==?getFather(b);
}
int?main()?{
????init();
????merge(3,?1);?//?3和1是親戚
????merge(1,?4);?//?1和4是親戚
????cout?<3)?<endl;?//?輸出3的團伙代表人+換行
????cout?<3,?1)?<endl;?//?輸出3和1是否是親戚+換行
}
并查集巧妙吧！我們既沒有構(gòu)建圖，也沒有構(gòu)建邊，自始至終只用到了f數(shù)組，又優(yōu)化了時間。
不要小瞧并查集代碼短，在很多時候并查集都會派上用場，比如著名的克魯斯卡爾算法，就是通過并查集判斷兩個頂點是否相連的。更重要的是體會并查集的思想，用這種思想來優(yōu)化代碼。
好了，今天的并查集就介紹到這里，希望大家能好好消化吸收，歡迎點個在看哦~~
推薦閱讀：
完全整理 | 365篇高質(zhì)技術(shù)文章目錄整理
專注服務(wù)器后臺技術(shù)棧知識總結(jié)分享
歡迎關(guān)注交流共同進步
碼農(nóng)有道?coding
碼農(nóng)有道，為您提供通俗易懂的技術(shù)文章，讓技術(shù)變的更簡單
嘿，你在看嗎