并查集
并查集是一種樹形的數(shù)據(jù)結構沛励，顧名思義，它用于處理一些不交集的 合并 及 查詢 問題钝侠。 它支持兩種操作：
- 查找（Find）：確定某個元素處于哪個子集疤坝；
- 合并（Union）：將兩個子集合并成一個集合。
并查集不支持集合的分離披摄，但是并查集在經(jīng)過修改后可以支持集合中單個元素的刪除操作（詳見 UVA11987 Almost Union-Find）亲雪。使用動態(tài)開點線段樹還可以實現(xiàn)可持久化并查集
查找
通俗地講一個故事：幾個家族進行宴會，但是家族普遍長壽疚膊，所以人數(shù)眾多义辕。由于長時間的分離以及年齡的增長，這些人逐漸忘掉了自己的親人寓盗，只記得自己的爸爸是誰了灌砖，而最長者（稱為「祖先」）的父親已經(jīng)去世，他只知道自己是祖先贞让。為了確定自己是哪個家族周崭，他們想出了一個辦法，只要問自己的爸爸是不是祖先喳张，一層一層的向上問续镇，直到問到祖先。如果要判斷兩人是否在同一家族销部，只要看兩人的祖先是不是同一人就可以了摸航。
在這樣的思想下，并查集的查找算法誕生了舅桩。
int fa[MAXN]; // 記錄某個人的爸爸是誰酱虎，特別規(guī)定，祖先的爸爸是他自己
int find(int x) {
// 尋找x的祖先
if (fa[x] == x) // 如果x是祖先則返回
return x;
else
return find(fa[x]); // 如果不是則x的爸爸問x的爺爺
}
顯然這樣最終會返回x的祖先擂涛。
路徑壓縮
這樣的確可以達成目的读串，但是顯然效率實在太低。為什么呢撒妈？因為我們使用了太多沒用的信息恢暖，我的祖先是誰與我父親是誰沒什么關系，這樣一層一層找太浪費時間狰右，不如我直接當祖先的兒子杰捂，問一次就可以出結果了。甚至祖先是誰都無所謂棋蚌，只要這個人可以代表我們家族就能得到想要的效果嫁佳。把在路徑上的每個節(jié)點都直接連接到根上挨队，這就是路徑壓縮。
這樣我們的代碼可以做這樣的修改
int fa[MAXN]; // 記錄某個人的爸爸是誰蒿往，特別規(guī)定盛垦，祖先的爸爸是他自己
int find(int x) {
// 尋找x的祖先
if (fa[x] == x) // 如果x是祖先則返回
return x;
else
return fa[x] = find(fa[x]);
}
合并
宴會上，一個家族的祖先突然對另一個家族說：我們兩個家族交情這么好熄浓，不如合成一家好了情臭。另一個家族也欣然接受了。
我們之前說過赌蔑，并不在意祖先究竟是誰，所以只要其中一個祖先變成另一個祖先的兒子就可以了竟秫。
void unionSet(int x, int y) {
//我們將學x娃惯，y所在的家族進行合并
//我們只需要找到他們的祖先find(x) = find(y)
x = find(x)
y = find(y)
fa[x] = y
}
啟發(fā)式合并（按秩合并）
一個祖先突然抖了個機靈：「你們家族人比較少，搬家到我們家族里比較方便肥败，我們要是搬過去的話太費事了趾浅。」
由于需要我們支持的只有集合的合并馒稍、查詢操作皿哨，當我們需要將兩個集合合二為一時，無論將哪一個集合連接到另一個集合的下面纽谒，都能得到正確的結果证膨。但不同的連接方法存在時間復雜度的差異。具體來說鼓黔，如果我們將一棵點數(shù)與深度都較小的集合樹連接到一棵更大的集合樹下央勒，顯然相比于另一種連接方案，接下來執(zhí)行查找操作的用時更邪幕（也會帶來更優(yōu)的最壞時間復雜度）崔步。
當然，我們不總能遇到恰好如上所述的集合————點數(shù)與深度都更小缎谷。鑒于點數(shù)與深度這兩個特征都很容易維護井濒，我們常常從中擇一，作為估價函數(shù)列林。而無論選擇哪一個瑞你，時間復雜度都為 O(n)，
如果只使用啟發(fā)式合并席纽，而不使用路徑壓縮捏悬，時間復雜度為O(mlog n) 。由于路徑壓縮單次合并可能造成大量修改润梯，有時路徑壓縮并不適合使用过牙。例如甥厦，在可持久化并查集、線段樹分治 + 并查集中寇钉，一般使用只啟發(fā)式合并的并查集刀疙。
std::vector<int> size(N, 1); // 記錄并初始化子樹的大小為 1
void unionSet(int x, int y) {
int xx = find(x)
int yy = find(y)
if(xx == yy) return
if (size[xx] > size[yy]) // 保證小的合到大的里
swap(xx, yy);
fa[xx] = yy;
size[yy] += size[xx];
}
