【模版】并查集及路徑壓縮

轉載 2014年08月19日 15:10:40

标簽：
資料結構 /
壓縮 /

6656
編輯
删除

Ps：在網上看到的寫的很好的并查集

并查集（Union-find Sets）是一種非常精巧而實用的資料結構，它主要用于處理一些不相交集合的合并問題。一些常見的用途有求連通子圖、求最小生成樹的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。

使用并查集時，首先會存在一組不相交的動态集合，一般都會使用一個整數表示集合中的一個元素。

每個集合可能包含一個或多個元素，并選出集合中的某個元素作為代表。每個集合中具體包含了哪些元素是不關心的，具體選擇哪個元素作為代表一般也是不關心的。我們關心的是，對于給定的元素，可以很快的找到這個元素所在的集合（的代表），以及合并兩個元素所在的集合，而且這些操作的時間複雜度都是常數級的。

并查集的基本操作有三個：

makeSet(s)：建立一個新的并查集，其中包含 s 個單元素集合。
unionSet(x, y)：把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交，如果相交則不合并。
find(x)：找到元素 x 所在的集合的代表，該操作也可以用于判斷兩個元素是否位于同一個集合，隻要将它們各自的代表比較一下就可以了。

并查集的實作原理也比較簡單，就是使用樹來表示集合，樹的每個節點就表示集合中的一個元素，樹根對應的元素就是該集合的代表，如圖 1 所示。

并查集【模版】并查集及路徑壓縮

圖 1 并查集的樹表示

圖中有兩棵樹，分别對應兩個集合，其中第一個集合為，代表元素是；第二個集合為，代表元素是。

樹的節點表示集合中的元素，指針表示指向父節點的指針，根節點的指針指向自己，表示其沒有父節點。沿着每個節點的父節點不斷向上查找，最終就可以找到該樹的根節點，即該集合的代表元素。

現在，應該可以很容易的寫出 makeSet 和 find 的代碼了，假設使用一個足夠長的數組來存儲樹節點（很類似之前講到的靜态連結清單），那麼 makeSet 要做的就是構造出如圖 2 的森林，其中每個元素都是一個單元素集合，即父節點是其自身：

并查集【模版】并查集及路徑壓縮

圖 2 構造并查集初始化

相應的代碼如下所示，時間複雜度是：

[html] view plain copy print ?

const int MAXSIZE = 500;
int uset[MAXSIZE];
void makeSet(int size) {
for(int i = 0;i < size;i++) uset[i] = i;
}

const int MAXSIZE = 500;

int uset[MAXSIZE];

 

void makeSet(int size) {

    for(int i = 0;i < size;i++) uset[i] = i;

}

接下來，就是 find 操作了，如果每次都沿着父節點向上查找，那時間複雜度就是樹的高度，完全不可能達到常數級。這裡需要應用一種非常簡單而有效的政策——路徑壓縮。

路徑壓縮，就是在每次查找時，令查找路徑上的每個節點都直接指向根節點，如圖 3 所示。

并查集【模版】并查集及路徑壓縮

圖 3 路徑壓縮

我準備了兩個版本的 find 操作實作，分别是遞歸版和非遞歸版，不過兩個版本目前并沒有發現有什麼明顯的效率差距，是以具體使用哪個完全憑個人喜好了。

[html] view plain copy print ?

int find(int x) {
if (x != uset[x]) uset[x] = find(uset[x]);
return uset[x];
}
int find(int x) {//查找根節點
int p = x, t;
while (uset[p] != p) p = uset[p];//傳回根節點；
while (x != p) { t = uset[x]; uset[x] = p; x = t; }//路徑壓縮
return x;
}

int find(int x) {

    if (x != uset[x]) uset[x] = find(uset[x]);

    return uset[x];

}

int find(int x) {//查找根節點

    int p = x, t;

    while (uset[p] != p) p = uset[p];//傳回根節點；

    while (x != p) { t = uset[x]; uset[x] = p; x = t; }//路徑壓縮

    return x;

}

最後是合并操作 unionSet，并查集的合并也非常簡單，就是将一個集合的樹根指向另一個集合的樹根，如圖 4 所示。

并查集【模版】并查集及路徑壓縮

圖 4 并查集的合并

這裡也可以應用一個簡單的啟發式政策——按秩合并。該方法使用秩來表示樹高度的上界，在合并時，總是将具有較小秩的樹根指向具有較大秩的樹根。簡單的說，就是總是将比較矮的樹作為子樹，添加到較高的樹中。為了儲存秩，需要額外使用一個與 uset 同長度的數組，并将所有元素都初始化為 0。

[html] view plain copy print ?

void unionSet(int x, int y) {
if ((x = find(x)) == (y = find(y))) return;
if (rank[x] > rank[y]) uset[y] = x;
else {
uset[x] = y;
if (rank[x] == rank[y]) rank[y]++;
}
}

void unionSet(int x, int y) {

    if ((x = find(x)) == (y = find(y))) return;

    if (rank[x] > rank[y]) uset[y] = x;

    else {

        uset[x] = y;

        if (rank[x] == rank[y]) rank[y]++;

    }

}

下面是按秩合并的并查集的完整代碼，這裡隻包含了遞歸的 find 操作。

[html] view plain copy print ?

const int MAXSIZE = 500;
int uset[MAXSIZE];
int rank[MAXSIZE];
void makeSet(int size) {
for(int i = 0;i < size;i++) uset[i] = i;
for(int i = 0;i < size;i++) rank[i] = 0;
}
int find(int x) {
if (x != uset[x]) uset[x] = find(uset[x]);
return uset[x];
}
void unionSet(int x, int y) {
if ((x = find(x)) == (y = find(y))) return;
if (rank[x] > rank[y]) uset[y] = x;
else {
uset[x] = y;
if (rank[x] == rank[y]) rank[y]++;
}
}

const int MAXSIZE = 500;

int uset[MAXSIZE];

int rank[MAXSIZE];

 

void makeSet(int size) {

    for(int i = 0;i < size;i++)  uset[i] = i;

    for(int i = 0;i < size;i++)  rank[i] = 0;

}

int find(int x) {

    if (x != uset[x]) uset[x] = find(uset[x]);

    return uset[x];

}

void unionSet(int x, int y) {

    if ((x = find(x)) == (y = find(y))) return;

    if (rank[x] > rank[y]) uset[y] = x;

    else {

        uset[x] = y;

        if (rank[x] == rank[y]) rank[y]++;

    }

}

除了按秩合并，并查集還有一種常見的政策，就是按集合中包含的元素個數（或者說樹中的節點數）合并，将包含節點較少的樹根，指向包含節點較多的樹根。這個政策與按秩合并的政策類似，同樣可以提升并查集的運作速度，而且省去了額外的 rank 數組。

這樣的并查集具有一個略微不同的定義，即若 uset 的值是正數，則表示該元素的父節點（的索引）；若是負數，則表示該元素是所在集合的代表（即樹根），而且值的相反數即為集合中的元素個數。相應的代碼如下所示，同樣包含遞歸和非遞歸的 find 操作：

[html] view plain copy print ?

const int MAXSIZE = 500;
int uset[MAXSIZE];
void makeSet(int size) {
for(int i = 0;i < size;i++) uset[i] = -1;
}
int find(int x) {
if (uset[x] < 0) return x;
uset[x] = find(uset[x]);
return uset[x];
}
int find(int x) {
int p = x, t;
while (uset[p] >= 0) p = uset[p];
while (x != p) {
t = uset[x];
uset[x] = p;
x = t;
}
return x;
}
void unionSet(int x, int y) {
if ((x = find(x)) == (y = find(y))) return;
if (uset[x] < uset[y]) {
uset[x] += uset[y];
uset[y] = x;
} else {
uset[y] += uset[x];
uset[x] = y;
}
}

const int MAXSIZE = 500;

int uset[MAXSIZE];

 

void makeSet(int size) {

    for(int i = 0;i < size;i++) uset[i] = -1;

}

int find(int x) {

    if (uset[x] < 0) return x;

    uset[x] = find(uset[x]);

    return uset[x];

}

int find(int x) {

    int p = x, t;

    while (uset[p] >= 0) p = uset[p];

    while (x != p) {

        t = uset[x];

        uset[x] = p;

        x = t;

    }

    return x;

}

void unionSet(int x, int y) {

    if ((x = find(x)) == (y = find(y))) return;

    if (uset[x] < uset[y]) {

        uset[x] += uset[y];

        uset[y] = x;

    } else {

        uset[y] += uset[x];

        uset[x] = y;

    }

}

如果要擷取某個元素 x 所在集合包含的元素個數，可以使用 -uset[find(x)] 得到。

并查集的空間複雜度是的，這個很顯然，如果是按秩合并的，占的空間要多一些。find 和 unionSet 操作都可以看成是常數級的，或者準确來說，在一個包含個元素的并查集中，進行次查找或合并操作，最壞情況下所需的時間為，這裡的是 Ackerman 函數的某個反函數，在極大的範圍内（比可觀察到的宇宙中估計的原子數量還大很多）都可以認為是不大于 4 的。具體的時間複雜度分析，請參見《算法導論》的 21.4 節帶路徑壓縮的按秩合并的分析。

作者：CYJB

出處：http://www.cnblogs.com/cyjb/

GitHub：https://github.com/CYJB/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。

附上另一種比較搞笑的講法

為了解釋并查集的原理，我将舉一個更有愛的例子。話說江湖上散落着各式各樣的大俠，有上千個之多。他們沒有什麼正當職業，整天背着劍在外面走來走去，碰到和自己不是一路人的，就免不了要打一架。但大俠們有一個優點就是講義氣，絕對不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”，隻要是能通過朋友關系串聯起來的，不管拐了多少個彎，都認為是自己人。這樣一來，江湖上就形成了一個一個的群落，通過兩兩之間的朋友關系串聯起來。而不在同一個群落的人，無論如何都無法通過朋友關系連起來，于是就可以放心往死了打。但是兩個原本互不相識的人，如何判斷是否屬于一個朋友圈呢？

我們可以在每個朋友圈内推舉出一個比較有名望的人，作為該圈子的代表人物，這樣，每個圈子就可以這樣命名“齊達内朋友之隊”“羅納爾多朋友之隊”……兩人隻要互相對一下自己的隊長是不是同一個人，就可以确定敵友關系了。

但是還有問題啊，大俠們隻知道自己直接的朋友是誰，很多人壓根就不認識隊長，要判斷自己的隊長是誰，隻能漫無目的的通過朋友的朋友關系問下去：“你是不是隊長？你是不是隊長？”這樣一來，隊長面子上挂不住了，而且效率太低，還有可能陷入無限循環中。于是隊長下令，重新組隊。隊内所有人實行分等級制度，形成樹狀結構，我隊長就是根節點，下面分别是二級隊員、三級隊員。每個人隻要記住自己的上級是誰就行了。遇到判斷敵友的時候，隻要一層層向上問，直到最高層，就可以在短時間内确定隊長是誰了。由于我們關心的隻是兩個人之間是否連通，至于他們是如何連通的，以及每個圈子内部的結構是怎樣的，甚至隊長是誰，并不重要。是以我們可以放任隊長随意重新組隊，隻要不搞錯敵友關系就好了。于是，門派産生了。

http://i3.6.cn/cvbnm/6f/ec/f4/1e9cfcd3def64d26ed1a49d72c1f6db9.jpg

并查集【模版】并查集及路徑壓縮

下面我們來看并查集的實作。 int pre[1000]; 這個數組，記錄了每個大俠的上級是誰。大俠們從1或者0開始編号（依據題意而定），pre[15]=3就表示15号大俠的上級是3号大俠。如果一個人的上級就是他自己，那說明他就是掌門人了，查找到此為止。也有孤家寡人自成一派的，比如歐陽鋒，那麼他的上級就是他自己。每個人都隻認自己的上級。比如胡青牛同學隻知道自己的上級是楊左使。張無忌是誰？不認識！要想知道自己的掌門是誰，隻能一級級查上去。 find這個函數就是找掌門用的，意義再清楚不過了（路徑壓縮算法先不論，後面再說）。

int find(int x) //查找我（x）的掌門

{

int r=x; //委托 r 去找掌門

while (pre[r ]!=r) //如果r的上級不是r自己（也就是說找到的大俠他不是掌門 = =）

r=pre[r ] ; // r 就接着找他的上級，直到找到掌門為止。

return r ; //掌門駕到~~~

}

再來看看join函數，就是在兩個點之間連一條線，這樣一來，原先它們所在的兩個闆塊的所有點就都可以互通了。這在圖上很好辦，畫條線就行了。但我們現在是用并查集來描述武林中的狀況的，一共隻有一個pre[]數組，該如何實作呢？還是舉江湖的例子，假設現在武林中的形勢如圖所示。虛竹小和尚與周芷若MM是我非常喜歡的兩個人物，他們的終極boss分别是玄慈方丈和滅絕師太，那明顯就是兩個陣營了。我不希望他們互相打架，就對他倆說：“你們兩位拉拉勾，做好朋友吧。”他們看在我的面子上，同意了。這一同意可非同小可，整個少林和峨眉派的人就不能打架了。這麼重大的變化，可如何實作呀，要改動多少地方？其實非常簡單，我對玄慈方丈說：“大師，麻煩你把你的上級改為滅絕師太吧。這樣一來，兩派原先的所有人員的終極boss都是師太，那還打個球啊！反正我們關心的隻是連通性，門派内部的結構不要緊的。”玄慈一聽肯定火大了：“我靠，憑什麼是我變成她手下呀，怎麼不反過來？我抗議！”抗議無效，上天安排的，最大。反正誰加入誰效果是一樣的，我就随手指定了一個。這段函數的意思很明白了吧？

void join(int x,int y) //我想讓虛竹和周芷若做朋友

{

int fx=find(x),fy=find(y); //虛竹的老大是玄慈，芷若MM的老大是滅絕

if(fx!=fy) //玄慈和滅絕顯然不是同一個人

pre[fx ]=fy; //方丈隻好委委屈屈地當了師太的手下啦

}

并查集【模版】并查集及路徑壓縮

【模版】并查集及路徑壓縮

繼續閱讀

「postOI」Cross Swapping

POJ 1703 Find them, Catch them（資料結構-并查集）

BZOJ 2303 [Apio2011]方格染色

The Suspects （并查集）

POJ 2513 Colored Sticks 字典樹hash 歐拉路徑

BZOJ 4537 [Hnoi2016]最小公倍數

The Suspects POJ - 1611（并查集）

POJ-1703 Find them, Catch them 經典并查集

poj2492(并查集)

codeevs 1069關押罪犯，關系并查集

并查集【模版】并查集 及路徑壓縮

【模版】并查集 及路徑壓縮

繼續閱讀

并查集【模版】并查集及路徑壓縮

【模版】并查集及路徑壓縮