什么是 “并查集” ？

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

本文作者封承成，年僅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)所在的組。

所以對(duì)于一個(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)伙的代表人。

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

剛剛我們合并了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)伙的工作就完成了?？偨Y(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)伙代表人怎么求呢？我們會(huì)發(fā)現(xiàn)另一個(gè)特征，任何一個(gè)團(tuán)伙的代表人a，都有f[a] = a。很好理解，團(tuán)伙代表人也是團(tuán)伙的一個(gè)成員，團(tuán)伙代表人所在團(tuán)伙的代表人就是它自己。

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

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

在例子中，我們想要知道1是否為團(tuán)伙代表人，就可以看f[1]是否等于1，很明顯，f[1] = 4，所以1不是該團(tuán)伙的代表人，我們要繼續(xù)“追本溯源”，對(duì)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;
}

const int N = 100; // 節(jié)點(diǎn)數(shù)量 int f[N]; int init() { // 初始化 for (int i=0; iint 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 << getFather(3) << endl; // 輸出3的團(tuán)伙代表人+換行 cout << query(3, 1) << endl; // 輸出3和1是否是親戚+換行 }

       點(diǎn)個(gè)[在看]，是對(duì)小灰最大的支持！