什么是 “并查集” ？

導(dǎo)語：并查集是一種精巧的算法，本身并不難理解，卻很常用，在許多場景下都能找到并查集的身影。

本文作者封承成，年僅12歲，非常感謝他的投稿。

并查集是什么

并查集，是一種判斷“遠(yuǎn)房親戚”的算法。

打個(gè)比方：你身邊的某個(gè)“朋友”，很有可能就是你父親的母親的姑媽的大姨的哥哥的表妹的孫子的女兒的父親的孫子。如果給定這么一張“家譜”（無向圖），如何判斷兩個(gè)頂點(diǎn)是不是“親戚”呢？用人話說，就是判斷一個(gè)圖中兩個(gè)點(diǎn)是否聯(lián)通（兩個(gè)頂點(diǎn)相互聯(lián)通則為親戚）。

并查集是專門用來解決這樣的問題的，和搜索不同，并查集在構(gòu)建圖的時(shí)候同時(shí)就標(biāo)記出了哪個(gè)“人”屬于哪個(gè)“團(tuán)伙”（一團(tuán)伙中的點(diǎn)兩兩聯(lián)通）。

并查集的操作

1. 初始化

并查集的思想是通過標(biāo)記確定該頂點(diǎn)所在的組。

所以對于一個(gè)n個(gè)點(diǎn)，m條邊的圖，我們需要新建一個(gè)長度為n的數(shù)組f（可以理解為father），f[n]代表點(diǎn)n的團(tuán)伙“代表人”，當(dāng)兩個(gè)點(diǎn)所在團(tuán)伙“代表人”相同，則這兩個(gè)點(diǎn)所在團(tuán)伙相同。

而在最開始，每個(gè)頂點(diǎn)間都是互相不連通的，所以每個(gè)頂點(diǎn)單獨(dú)屬于一個(gè)團(tuán)伙，每個(gè)頂點(diǎn)理所應(yīng)當(dāng)成為自己團(tuán)伙的“代表人”，所以我們把f[n]的初始值賦為n。

2. 合并團(tuán)伙

我們以連接3和1這兩個(gè)點(diǎn)做例子：

在連接點(diǎn)3和點(diǎn)1時(shí)，3和1形成了一個(gè)團(tuán)伙，而3和1的團(tuán)伙代表人f[3]和f[1]就應(yīng)該統(tǒng)一，具體是讓3做代表人還是讓1做代表人隨便，我們讓1做代表人。f[3] = 1，這條語句可以理解為讓1所在團(tuán)伙的代表人同時(shí)成為3所在團(tuán)伙的代表人。

（箭頭只是體現(xiàn)了f數(shù)組中“團(tuán)伙成員”和“代表人”的關(guān)系，其實(shí)這個(gè)圖是無向圖）

可是，像f[a] = b這樣合并真的對嗎？請讀者考慮這樣一種情況。

剛剛我們合并了3和1，現(xiàn)在我們需要合并3和2。如果按照f[a] = b這樣合并，那么，f[3]就被賦值為了2。這樣，f[3]原本的值1就被覆蓋了，也就是說，1和3的團(tuán)伙就被硬生生地“拆散”了。

下面我們換一個(gè)例子：合并3和4。此時(shí)我們不應(yīng)該令f[3] =4，應(yīng)該讓f[3的團(tuán)伙代表人] = (4的團(tuán)伙代表人)，如下圖。

這樣，合并兩個(gè)團(tuán)伙的工作就完成了。總結(jié)起來就一句話：f[a的團(tuán)伙代表人] = (b的團(tuán)伙代表人)。

3. 查找團(tuán)伙代表人

緊接著，又一個(gè)問題浮出水面：根據(jù)上面的公式f[a的團(tuán)伙代表人] = (b的團(tuán)伙代表人)，可是a、b的團(tuán)伙代表人怎么求？是f[a]嗎？不不不，這里的情況變得復(fù)雜了。大家再次考慮一種特殊情況。

在這種情況下，3的團(tuán)伙代表人是誰？1還是4？正確答案是4。因?yàn)椋?/span>一個(gè)團(tuán)伙中每一個(gè)點(diǎn)都直接或間接地“指向”這個(gè)團(tuán)伙的代表人。（1,3,4）這個(gè)團(tuán)伙中，1直接地指向4，3間接地指向4，所以4才是這個(gè)團(tuán)伙里的代表人。

那么，點(diǎn)x的團(tuán)伙代表人怎么求呢？我們會發(fā)現(xiàn)另一個(gè)特征，任何一個(gè)團(tuán)伙的代表人a，都有f[a] = a。很好理解，團(tuán)伙代表人也是團(tuán)伙的一個(gè)成員，團(tuán)伙代表人所在團(tuán)伙的代表人就是它自己。

而對于其他點(diǎn)a，f[a]均不等于a。并且如果一個(gè)頂點(diǎn)a有f[a] ≠ a，那么這個(gè)點(diǎn)一定不是團(tuán)伙的代表人，因?yàn)閒[a]不會間接地或直接地指向a（并查集保證不會存在環(huán)）。

根據(jù)這一特性，我們可以判斷點(diǎn)a是否為某個(gè)團(tuán)伙的代表人。

在例子中，我們想要知道1是否為團(tuán)伙代表人，就可以看f[1]是否等于1，很明顯，f[1] = 4，所以1不是該團(tuán)伙的代表人，我們要繼續(xù)“追本溯源”，對5進(jìn)行判斷。這個(gè)過程就是一種遞歸的尋找過程。

知道了這個(gè)特性，我們就可以寫出相應(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;
}

這是一個(gè)遞歸函數(shù)，如果f[x] = x，說明這個(gè)點(diǎn)已經(jīng)是該團(tuán)伙的代表人，直接返回就好了，如果它不是該團(tuán)伙的代表人，那么就返回自己指向的點(diǎn)的團(tuán)伙代表人。

在求getFather(3)時(shí)，f[3] != 3，返回getFather(f[3])也就是getFather(1)；

在求getFather(1)時(shí)，f[1] != 1，返回getFather(f[1])也就是getFather(4)；

在求getFather(4)時(shí)，f[4] == 4，返回4。遞歸結(jié)束。最后計(jì)算出3的團(tuán)伙代表人是4。

4. 查詢頂點(diǎn)是否在同一團(tuán)伙

并查集的最后一種操作叫做查詢，就是查詢兩個(gè)點(diǎn)是否連通（在同一團(tuán)伙）。

前面已經(jīng)講了，當(dāng)兩個(gè)點(diǎn)所在團(tuán)伙“代表人”相同，則這兩個(gè)點(diǎn)所在團(tuán)伙相同。判斷兩個(gè)點(diǎn)a、b在同一團(tuán)伙的方法就是：

getFather(a)?==?getFather(b)?

5. 完整代碼

const?int?N?=?100;?//?節(jié)點(diǎn)數(shù)量
int?f[N];

int?init()?{
????//?初始化
????for?(int?i=0;?i????????f[i]?=?i;
}

int?getFather(int?x)?{
????//?查詢所在團(tuán)伙代表人
????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的團(tuán)伙代表人+換行
????cout?<3,?1)?<endl;?//?輸出3和1是否是親戚+換行
}

并查集巧妙吧！我們既沒有構(gòu)建圖，也沒有構(gòu)建邊，自始至終只用到了f數(shù)組，又優(yōu)化了時(shí)間。

不要小瞧并查集代碼短，在很多時(shí)候并查集都會派上用場，比如著名的克魯斯卡爾算法，就是通過并查集判斷兩個(gè)頂點(diǎn)是否相連的。更重要的是體會并查集的思想，用這種思想來優(yōu)化代碼。

好了，今天的并查集就介紹到這里，希望大家能好好消化吸收，歡迎點(diǎn)個(gè)在看哦~~

掃碼關(guān)注公眾號，訂閱更多精彩內(nèi)容。