最近做了點并查集的題，感覺也挺簡單的。下面對我這段時間關于并查集的學習，做一下小結。

并查集的作用：并和查，即合并和查找，將一些集合合并，快速查找或判斷某兩個集合的關系，或某元素與集合的關系，或某兩個元素的關系。

并查集的結構：并查集主要操作對象是森林，樹的結構賦予它獨特的能力，對整個集合操作轉換為對根節點(或稱該集合的代表元素)的操作，一個集合里的元素關系不一定確定，但相對于根節點的關系很明了，這也是為了查找方便。

并查集優化方法：按秩合并和路徑壓縮的配合使用，使得查找過程優化到極致。按秩合并，每次將深度小的樹合并到深度大的樹里面去，使得整棵樹盡量矮；路徑壓縮，將當前節點到根節點路徑上的所有點直接連到根節點上，使得每個點到根節點的距離更短，在下一次查找的時候更快。

如何快速確定偏移量公式：

例：現在要合并節點x,y, 找到根節點fx = Find(x); fy = Find(y);一般情況下，根節點的偏移量都保持為0, offset[foot] = 0;如果要使得x和y的偏移量為t，假設fx指向fy，則可以寫出公式offset[x] + offset[fx] - offset[y] = t，則offset[fx] = (offset[y] + t - offset[x]) % n; 這個n即為總共有多少類，如：在poj1182 食物鏈中n = 3,，在poj2492 A Bug's Life中n = 2, 這樣fx的偏移量就計算出來了，只需要改其中一個根節點的偏移量，這里是fx，因為假設是fx指向fy。

非遞歸路勁壓縮：

View Code 1 代碼 2 3 int Find(int x){ 4 int r = x; 5 while (r != bin[r]){ 6 r = bin[r]; 7 } 8 int y = x; 9 while (y != bin[y]){ 10 y = bin[y]; 11 bin[y] = r; 12 } 13 return r; 14 }

遞歸式路徑壓縮：

intFind(intx){
if(x !=bin[x]){
returnbin[x] =Find(bin[x]);
}
returnx;
}

轉載于:https://www.cnblogs.com/0803yijia/archive/2012/08/03/2622171.html

總結

以上是生活随笔為你收集整理的并查集小结（转）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。