[本文新址： http://www.ahathinking.com/archives/10.html ]
并查集：(union-find sets)
一種簡(jiǎn)單的用途廣泛的集合. 并查集是若干個(gè)不相交集合蚜迅，能夠?qū)崿F(xiàn)較快的合并和判斷元素所在集合的操作滓侍，應(yīng)用很多，如其求無(wú)向圖的連通分量個(gè)數(shù)等湾宙。最完美的應(yīng)用當(dāng)屬：實(shí)現(xiàn)Kruskar算法求最小生成樹。
并查集的精髓：
Make_Set(x) ：把每一個(gè)元素初始化為一個(gè)集合
初始化后每一個(gè)元素的父親節(jié)點(diǎn)是它本身悄晃，每一個(gè)元素的祖先節(jié)點(diǎn)也是它本身凤价。
int father[MAX]; /* father[x]表示x的父節(jié)點(diǎn)*/
int rank[MAX]; /* rank[x]表示x的秩*/
/* 初始化集合*/
void Make_Set(int x){
father[x] = x; //根據(jù)實(shí)際情況指定的父節(jié)點(diǎn)可變化
rank[x] = 0; //根據(jù)實(shí)際情況初始化秩也有所變化
}
Find_Set(x){ 查找一個(gè)元素所在的集合
查找一個(gè)元素所在的集合，其精髓是找到這個(gè)元素所在集合的祖先酗捌！這個(gè)才是并查集判斷和合并的最終依據(jù)呢诬。判斷兩個(gè)元素是否屬于同一集合涌哲，只要看他們所在集合的祖先是否相同即可。合并兩個(gè)集合尚镰，也是使一個(gè)集合的祖先成為另一個(gè)集合的祖先.
Find_Set(x)時(shí)路徑壓縮尋找祖先時(shí)我們一般采用遞歸查找阀圾，但是當(dāng)元素很多亦或是整棵樹變?yōu)橐粭l鏈時(shí)，每次Find_Set(x)都是O(n)的復(fù)雜度狗唉，有沒(méi)有辦法減小這個(gè)復(fù)雜度呢初烘？答案是肯定的，這就是路徑壓縮分俯，即當(dāng)我們經(jīng)過(guò)"遞推"找到祖先節(jié)點(diǎn)后肾筐，"回溯"的時(shí)候順便將它的子孫節(jié)點(diǎn)都直接指向祖先，這樣以后再次Find_Set(x)時(shí)復(fù)雜度就變成O(1)了缸剪，如下圖所示吗铐；可見，路徑壓縮方便了以后的查找
Union(x,y) 合并x,y所在的兩個(gè)集合
合并兩個(gè)不相交集合操作很簡(jiǎn)單：利用Find_Set找到其中兩個(gè)集合的祖先杏节，將一個(gè)集合的祖先指向另一個(gè)集合的祖先唬渗。
Union(x,y)時(shí) 按秩合并即合并的時(shí)候?qū)⒃厣俚募虾喜⒌皆囟嗟募现校@樣合并之后樹的高度會(huì)相對(duì)較小奋渔。
/* 查找x元素所在的集合,回溯時(shí)壓縮路徑*/
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]); //這個(gè)回溯時(shí)的壓縮路徑是精華
}
return father[x];
}
/*
按秩合并x,y所在的集合
下面的那個(gè)if else結(jié)構(gòu)不是絕對(duì)的谣妻，具體根據(jù)情況變化
但是，宗旨是不變的即卒稳，按秩合并蹋半，實(shí)時(shí)更新秩。
*/
void Union(int x, int y)
{
x = Find_Set(x);
y = Find_Set(y);
if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}
