? ? ? ? 并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相交集合(Disjoint Sets)的合并及查詢問題。常常在使用中以森林來表示届谈。
? ? ? ? 舉個例子,某鄉(xiāng)鎮(zhèn)有多個村子弯汰,為了出行方便艰山,需要進(jìn)行修路,使所有村子連在一起咏闪。
????????現(xiàn)在曙搬,按照如下pair修路,按順序如果兩村之間已經(jīng)可以互相到達(dá)則不需要再修路。(不將就距離問題纵装,只看是否連通)
? ? ? ? 1.5? ? 2.4? ? 1.6? ? 6.7? ? 1.7????3.4? ? 3.6? ? 1.2
? ? ? ? 如圖進(jìn)行連接 征讲,綠色的為修路的路線,紅色的為按順序不必要修的路線橡娄。
? ? ? ? 整體路線大概為2-4-3-6-1(7)-5诗箍。
? ? ? ? 正如標(biāo)題所說,形成的一種樹狀圖形挽唉,其中節(jié)點6的度為2滤祖。
? ? ? ? 那么問題來了,我們?nèi)绾尾拍苤榔孔眩@個兩個節(jié)點是否已經(jīng)是連在一條線上的呢匠童?
????????這里我們采用數(shù)組的方法來解決。
? ? ? ? 首先塑顺,我們需要一個數(shù)組汤求,數(shù)組的下標(biāo)即是村莊(節(jié)點)。然后严拒,我們的到需要修路的村莊pair扬绪,我們先驚醒判定,如果兩村莊不在一條線上糙俗,就綁在一條線上(綁定方法為找頭)勒奇,如果已經(jīng)在一條線上,就不做處理巧骚。
????????找頭的時候赊颠,我們需要先對數(shù)組進(jìn)行初始化,初始化為數(shù)組的值為數(shù)組的下標(biāo)劈彪。而這個下標(biāo)節(jié)點對應(yīng)的值便是這個節(jié)點的上級頭目竣蹦,一直向上尋找,當(dāng)下標(biāo)節(jié)點的值等于下標(biāo)時沧奴,便是頭痘括。
for(int i = 0; i < n; i++)
? ? v[i] = i;
? ? ? ? 然后,我們通過調(diào)用函數(shù)的方式滔吠,對得到的一組村莊進(jìn)行判定纲菌,如果二者的頭是同一個數(shù)組下標(biāo),則為統(tǒng)一條線的村莊疮绷,如果頭的下標(biāo)不同翰舌,則是兩條不同的線,可以進(jìn)行連線冬骚。
連線的方式也很普通椅贱,由于找頭之后懂算,節(jié)點目前的位置在頭處,只需將其中一個頭連接到另一個頭上即可庇麦。
int getf(int v){
????if(v == f[v])
????????return v;
????return f[v] = getf(f[v]);
}
void merge(int v,int u){
????int t1 = getf(v);
????int t2 = getf(u);
????if(t1 != t2)
????????f[t1] = t2;
}
不必?fù)?dān)心计技,兩個頭誰連接到誰的問題,因為都是頭山橄,無論誰連接到誰垮媒,被連接的部分不變,連接的部分得到一個新頭驾胆。如圖所示:
????圖中涣澡,1與2已經(jīng)相連,需要對2和3進(jìn)行連接丧诺,已經(jīng)查到2的頭為1(f【2】=1,f【1】=1)奄薇,3的頭為3(f【3】=3)驳阎,我們得到兩種連接方式,分別為
1馁蒂、連接結(jié)果為f【2】=1? ? f【1】=1????f【3】=1? ? 2(3)-1
2呵晚、連接結(jié)果為f【2】=1? ? f【1】=3? ? f【3】=3? ? 2-1-3
按照以上操作將需要處理的數(shù)據(jù)處理完,我們就通過并查集獲得多條線(稱為樹更合適)沫屡,這些線在一起饵隙,組成森林,我們通過遍歷的方式沮脖,對每個數(shù)組下標(biāo)進(jìn)行遍歷金矛,如果此下標(biāo)的頭第一次出現(xiàn),計數(shù)器++勺届,如果已經(jīng)出現(xiàn)驶俊,跳過,遍歷結(jié)束免姿,我們即可得到森林里有多少顆樹饼酿。
并查集可以做很多題目
1.暢通工程(修路)
2.食物鏈判斷
3.判斷是否為樹
4.將很多人按照熟悉的人進(jìn)行分組
等等。胚膊。故俐。
by:有我wa