如果用連續(xù)的整數(shù)對(duì)元素進(jìn)行編號(hào)歌亲。比如有N個(gè)元素礼旅，則依次分配ID為 0,1,2...N-1炊苫。
為了方便實(shí)現(xiàn)闰集，我們將 【根節(jié)點(diǎn)的ID】作為【集合的ID】，見下方init()接口娜汁。
1.并查集有merge 和 find 兩個(gè)函數(shù)
find(x) ：通過(guò) x 的父節(jié)點(diǎn)，父節(jié)點(diǎn)的父節(jié)點(diǎn) ... ...，一直找到根節(jié)點(diǎn)并返回其ID仁锯。
merge(u,v)：通過(guò) find 函數(shù)找到 u，v 的根節(jié)點(diǎn) root_u, root_v翔悠。如果兩者的根節(jié)點(diǎn)不相同业崖，則將 root_u 的父節(jié)點(diǎn)設(shè)為 root_v。如果相同蓄愁，則無(wú)需任何操作双炕。
綜上，并查集不關(guān)心節(jié)點(diǎn)有哪些兒子撮抓，只關(guān)心節(jié)點(diǎn)的父親是誰(shuí)妇斤，所以并查集只需要一個(gè)數(shù)組 int father[n];
father[i]記錄節(jié)點(diǎn)i的父節(jié)點(diǎn)；特殊的丹拯，當(dāng) i 是根節(jié)點(diǎn)時(shí)站超，father[i] 的值為 i。
2.那如何快速查詢兩個(gè)元素是否來(lái)自同一父親呢乖酬？
這個(gè)簡(jiǎn)單死相，直接比較所屬集合ID是否相同即可。
// 初始時(shí)咬像，每個(gè)節(jié)點(diǎn)都構(gòu)成了一棵樹算撮，即每個(gè)節(jié)點(diǎn)都是一個(gè)根節(jié)點(diǎn)
int N = 1000;
void init(int N)
{
for (int i = 0; i < N; i++) { // 此處初始化，默認(rèn)是使用「根節(jié)點(diǎn)的ID」 作為 「集合的ID」
fa[i] = i;
}
}
// 找到元素x所屬的父集合id
int find(int x)
{
int r = x;
while (father[r] != r) {
r = father[r];
}
return r;
}
// 基于 find(x) 函數(shù)县昂，實(shí)現(xiàn) merge(u,v) 钮惠，很簡(jiǎn)單
void merge(int u, int v)
{
int ru = find(u);
int rv = find(v);
if (ru != rv) {
father[ru] = rv;
}
return;
}
【路徑壓縮】的核心思想：并查集其實(shí)也不關(guān)心節(jié)點(diǎn)的父親是誰(shuí)，它真正關(guān)心的是 【節(jié)點(diǎn)的根是誰(shuí)】七芭。既然這樣素挽，father[i] 直接記錄節(jié)點(diǎn) i 的根不就行了嘛。
// 第一個(gè) while：找到 x 所在樹的根節(jié)點(diǎn) r
// 第二個(gè) while：將 x → r 路徑上的所有節(jié)點(diǎn)的 father 更新為 r
int find(int x) {
int r = x;
while(father[r] != r) {
r = father[r];
}
while(father[x] != x) { // 這里是路徑壓縮處理,為將來(lái)查找實(shí)現(xiàn)O(n)到O(1)的轉(zhuǎn)變
int t = father[x];
father[x] = r;
x = t;
}
return x;
}
// 基于 find(x) 函數(shù)狸驳，實(shí)現(xiàn) merge(u,v)
bool merge(int u, int v) {
int ru = find(u);
int rv = find(v);
if (ru != rv) {
father[ru] = rv;
return true;
}
return false;
}
yo peace预明！
