什么是 “并查集” ?
并查集,是一種可以使用代表元來(lái)表示不相交集的數(shù)據(jù)結(jié)構(gòu),在一些只需要查詢兩個(gè)元素是否屬于同一個(gè)集合的情況下它很有用。比如給定一個(gè)無(wú)向圖,判斷兩個(gè)頂點(diǎn)是否屬于同一個(gè)連通分量。
在很多算法里面都會(huì)用到它,比如Kruskal最小生成樹算法。
并查集被很多OIer認(rèn)為是最簡(jiǎn)潔而優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)之一,主要用于解決一些元素分組的問(wèn)題。它管理一系列不相交的集合,并支持兩種操作:
合并(Union):把兩個(gè)不相交的集合合并為一個(gè)集合。
查詢(Find):查詢兩個(gè)元素是否在同一個(gè)集合中。
當(dāng)然,這樣的定義未免太過(guò)學(xué)術(shù)化,看完后恐怕不太能理解它具體有什么用。所以我們先來(lái)看看并查集最直接的一個(gè)應(yīng)用場(chǎng)景:親戚問(wèn)題。
并查集的操作
1. 初始化
并查集的思想是通過(guò)標(biāo)記確定該頂點(diǎn)所在的組。
所以對(duì)于一個(gè)n個(gè)點(diǎn),m條邊的圖,我們需要新建一個(gè)長(zhǎng)度為n的數(shù)組f(可以理解為father),f[n]代表點(diǎn)n的團(tuán)伙“代表人”,當(dāng)兩個(gè)點(diǎn)所在團(tuán)伙“代表人”相同,則這兩個(gè)點(diǎn)所在團(tuán)伙相同。
而在最開(kāi)始,每個(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,這條語(yǔ)句可以理解為讓1所在團(tuán)伙的代表人同時(shí)成為3所在團(tuán)伙的代表人。
(箭頭只是體現(xiàn)了f數(shù)組中“團(tuán)伙成員”和“代表人”的關(guān)系,其實(shí)這個(gè)圖是無(wú)向圖)
可是,像f[a] = b這樣合并真的對(duì)嗎?請(qǐng)大家考慮這樣一種情況。
剛剛我們合并了3和1,現(xiàn)在我們需要合并3和2。如果按照f(shuō)[a] = b這樣合并,那么,f[3]就被賦值為了2。這樣,f[3]原本的值1就被覆蓋了,也就是說(shuō),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é)起來(lái)就一句話:f[a的團(tuán)伙代表人] = (b的團(tuán)伙代表人)。
3. 查找團(tuán)伙代表人
緊接著,又一個(gè)問(wèn)題浮出水面:根據(jù)上面的公式f[a的團(tuán)伙代表人] = (b的團(tuán)伙代表人),可是a、b的團(tuán)伙代表人怎么求?是f[a]嗎?不不不,這里的情況變得復(fù)雜了。大家再次考慮一種特殊情況。
在這種情況下,3的團(tuán)伙代表人是誰(shuí)?1還是4?正確答案是4。因?yàn)?,一個(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è)過(guò)程就是一種遞歸的尋找過(guò)程。
知道了這個(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,說(shuō)明這個(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)介紹過(guò),當(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<N; 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 << getFather(3) << endl; // 輸出3的團(tuán)伙代表人+換行 cout << query(3, 1) << endl; // 輸出3和1是否是親戚+換行 }
是不是覺(jué)得并查集非常的巧妙!我們既沒(méi)有構(gòu)建圖,也沒(méi)有構(gòu)建邊,自始至終只用到了f數(shù)組,又優(yōu)化了時(shí)間。
不要小瞧并查集代碼短,在很多時(shí)候并查集都會(huì)派上用場(chǎng),比如著名的克魯斯卡爾算法,就是通過(guò)并查集判斷兩個(gè)頂點(diǎn)是否相連的。更重要的是體會(huì)并查集的思想,用這種思想來(lái)優(yōu)化代碼。
C語(yǔ)言網(wǎng)提供由在職研發(fā)工程師或ACM藍(lán)橋杯競(jìng)賽優(yōu)秀選手錄制的視頻教程,并配有習(xí)題和答疑,點(diǎn)擊了解:
一點(diǎn)編程也不會(huì)寫的:零基礎(chǔ)C語(yǔ)言學(xué)練課程
解決困擾你多年的C語(yǔ)言疑難雜癥特性的C語(yǔ)言進(jìn)階課程
從零到寫出一個(gè)爬蟲的Python編程課程
只會(huì)語(yǔ)法寫不出代碼?手把手帶你寫100個(gè)編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍(lán)橋杯ACM、信息學(xué)奧賽的必學(xué)課程:算法競(jìng)賽課入門課程
手把手講解近五年真題的藍(lán)橋杯輔導(dǎo)課程