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

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

并查集是什么

并查集，是一種判斷“遠房親戚”的算法。

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

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

并查集的操作

1. 初始化

并查集的思想是通過標記確定該頂點所在的組。

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

而在最開始，每個頂點間都是互相不連通的，所以每個頂點單獨屬于一個團伙，每個頂點理所應當成為自己團伙的“代表人”，所以我們把f[n]的初始值賦為n。

2. 合并團伙

我們以連接3和1這兩個點做例子：

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

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

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

下面我們換一個例子：合并3和4。此時我們不應該令f[3] =4，應該讓f[3的團伙代表人] = (4的團伙代表人)。

這樣，合并兩個團伙的工作就完成了?？偨Y起來就一句話：f[a的團伙代表人] = (b的團伙代表人)。

3. 查找團伙代表人

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

在這種情況下，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進行判斷。這個過程就是一種遞歸的尋找過程。

知道了這個特性，我們就可以寫出相應的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é)點數(shù)量 int f[N]; int init() { // 初始化 for (int i=0; iint 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 << getFather(3) << endl; // 輸出3的團伙代表人+換行 cout << query(3, 1) << endl; // 輸出3和1是否是親戚+換行 }

       點個[在看]，是對小灰最大的支持！