並查集（Disjoint set或者Union-find set）是一種樹型的數據結構，常用於處理一些不相交集合（Disjoint Sets）的合併及查詢問題。
基本操作
並查集是一種非常簡單的數據結構，它主要涉及兩個基本操作，分別為：
A． 合併兩個不相交集合
先設置一個數組Father[x]，表示x的“父親”的編號。 那麼，合併兩個不相交集合的方法就是，找到其中一個集合最父親的父親（也就是最久遠的祖先），將另外一個集合的最久遠的祖先的父親指向它。
C語言代碼如下:
void Union(int x,int y)
{
fx = getfather(x);
fy = getfather(y);
if (fy != fx) {
father[fx]=fy;
}
}
B． 判斷兩個元素是否屬於同一個集合
尋找兩個元素的最久遠祖先是否相同。尋找祖先可以採用遞歸實現。
bool same(int x,int y)
{
return getfather(x)==getfather(y);
}
並查集的優化
A 路徑壓縮
尋找祖先時採用遞歸，但是一旦元素一多起來，或退化成一條鏈，每次GetFather都將會使用O(n)的複雜度，這顯然不是我們想要的。
對此，我們必須要進行路徑壓縮，即我們找到最久遠的祖先時“順便”把它的子孫直接連接到它上面。這就是路徑壓縮。
C語言代碼如下:
int getfather(int v)
{
if (father[v] != v)
{
father[v]=getfather(father[v]);//路徑壓縮
}
return father[v];
}
Rank合併
合併時將元素所在深度小的集合合併到元素所在深度大的集合。
void Union(int x ,int y)
{
fx = getfather(x);
fy = getfather(y);
if (rank[fx]>rank[fy])
father[fy] = fx;
else
{
father[fx] = fy;
if(rank[fx]==rank[fy])
++rank[fy]; ////若兩樹一樣高，那麼合併後，高度加一
}
}
應用
對並查集而言，一個簡單的應用就是判斷無向圖的連通分量個數，或者判斷無向圖中任何兩個頂點是否連通。
閱讀更多 半杯茶的小酒杯 的文章
