? ? ? ? 并查集是一種樹型的數(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
