并查集：(union-find sets)是一種簡(jiǎn)單的用途廣泛的集合. 并查集是若干個(gè)不相交集合，能夠?qū)崿F(xiàn)較快的合并和判斷元素所在集合的操作，應(yīng)用很多，如其求無(wú)向圖的連通分量個(gè)數(shù)、最小公共祖先、帶限制的作業(yè)排序，還有最完美的應(yīng)用：實(shí)現(xiàn)Kruskar算法求最小生成樹(shù)。其實(shí)，這一部分《算法導(dǎo)論》講的很精煉。
一般采取樹(shù)形結(jié)構(gòu)來(lái)存儲(chǔ)并查集，在合并操作時(shí)可以利用樹(shù)的節(jié)點(diǎn)數(shù)(加權(quán)規(guī)則)或者利用一個(gè)rank數(shù)組來(lái)存儲(chǔ)集合的深度下界--啟發(fā)式函數(shù)，在查找操作時(shí)進(jìn)行路徑壓縮使后續(xù)的查找操作加速。這樣優(yōu)化實(shí)現(xiàn)的并查集，空間復(fù)雜度為O(N)，建立一個(gè)集合的時(shí)間復(fù)雜度為O(1)，N次合并M查找的時(shí)間復(fù)雜度為O(M Alpha(N))，這里Alpha是Ackerman函數(shù)的某個(gè)反函數(shù)，在很大的范圍內(nèi)這個(gè)函數(shù)的值可以看成是不大于4的，所以并查集的操作可以看作是線性的。
它支持以下三種操作:
－Union (Root1, Root2) //合并操作；把子集合Root2和子集合Root1合并.要求：Root1和 Root2互不相交,否則不執(zhí)行操作.
－Find (x) //搜索操作；搜索元素x所在的集合,并返回該集合的名字--根節(jié)點(diǎn).
－UFSets (s) //構(gòu)造函數(shù)。將并查集中s個(gè)元素初始化為s個(gè)只有一個(gè)單元素的子集合.
－對(duì)于并查集來(lái)說(shuō)，每個(gè)集合用一棵樹(shù)表示。
－集合中每個(gè)元素的元素名分別存放在樹(shù)的結(jié)點(diǎn)中，此外，樹(shù)的每一個(gè)結(jié)點(diǎn)還有一個(gè)指向其雙親結(jié)點(diǎn)的指針。
－為簡(jiǎn)化討論，忽略實(shí)際的集合名，僅用表示集合的樹(shù)的根來(lái)標(biāo)識(shí)集合。
以下給出我的兩種實(shí)現(xiàn):
//Abstract: UFSet
//Author:Lifeng Wang （Fandywang）
// Model One 與Model 2 路徑壓縮方式不同,合并標(biāo)準(zhǔn)不同
const int MAXSIZE = 500010;
int rank[MAXSIZE]; // 節(jié)點(diǎn)高度的上界
int parent[MAXSIZE]; // 根節(jié)點(diǎn)
int FindSet(int x){// 查找+遞歸的路徑壓縮
if( x != parent[x] ) parent[x] = FindSet(parent[x]);
return parent[x];
}
void Union(int root1, int root2){
int x = FindSet(root1), y = FindSet(root2);
if( x == y ) return ;
if( rank[x] > rank[y] ) parent[y] = x;
else{
parent[x] = y;
if( rank[x] == rank[y] ) ++rank[y];
}
}
void Initi(void){
memset(rank, 0, sizeof(rank));
for( int i=0; i < MAXSIZE; ++i ) parent[i] = i;
}
// Model Two
const int MAXSIZE = 30001;
int pre[MAXSIZE]; //根節(jié)點(diǎn)i,pre[i] = -num,其中num是該樹(shù)的節(jié)點(diǎn)數(shù)目;
//非根節(jié)點(diǎn)j,pre[j] = k,其中k是j的父節(jié)點(diǎn)
int Find(int x){//查找+非遞歸的路徑壓縮
int p = x;
while( pre[p] > 0 ) p = pre[p];
while( x != p ){
int temp = pre[x]; pre[x] = p; x = temp;
}
return x;
}
void Union(int r1, int r2){
int a = Find(r1); int b = Find(r2);
if( a == b ) return ;
//加權(quán)規(guī)則合并
if( pre[a] < pre[b] ){
pre[a] += pre[b]; pre[b] = a;
}
else {
pre[b] += pre[a]; pre[a] = b;
}
}
void Initi(void)
{
for( int i=0; i < N; ++i ) pre[i] = -1;
}
并查集的一些題目和我的相關(guān)解題報(bào)告:
POJ 1611 The Suspects 最基礎(chǔ)的并查集
POJ 2524 Ubiquitous Religions 最基本的并查集
POJ 1182 食物鏈 并查集的拓展
注意: 只有一組數(shù)據(jù);
要充分利用題意所給條件:有三類(lèi)動(dòng)物A,B,C，這三類(lèi)動(dòng)物的食物鏈
構(gòu)成了有趣的環(huán)形。A吃B， B吃C，C吃A。也就是說(shuō):只有三個(gè)group
POJ 2492 A Bug's Life 并查集的拓展
法一:深度優(yōu)先遍歷
每次遍歷記錄下該點(diǎn)是男還是女，只有:男-〉女，女-〉男滿足，否則，找到同性戀，結(jié)束程序。
法二:二分圖匹配
法三:并查集的拓展:和1182很像，只不過(guò)這里就有兩組，而1182是三組,1611無(wú)限制
POJ 1861 Network == zju_1542 并查集+自定義排序+貪心求"最小生成樹(shù)"
答案不唯一，不過(guò)在ZOJ上用QSORT()和SORT()都能過(guò)，在POJ上只有SORT()才能過(guò)...
POJ 1703 Find them, Catch them 并查集的拓展
這個(gè)和POJ 2492 A Bug's Life很像，就是把代碼稍微修改了一下就AC了！
注意：And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. 就是說(shuō)只有兩個(gè)組。
POJ 2236 Wireless Network 并查集的應(yīng)用
需要注意的地方：1、并查集；2、N的范圍，可以等于1001；3、從N+1行開(kāi)始，第一個(gè)輸入的可以是字符串。
POJ 1988 Cube Stacking 并查集很好的應(yīng)用
1、與 銀河英雄傳說(shuō)==NOI2002 Galaxy一樣；2、增加了一個(gè)數(shù)組behind[x],記錄戰(zhàn)艦x在列中的相對(duì)位置；3、詳細(xì)解題報(bào)告見(jiàn)銀河英雄傳說(shuō)。
JOJ 1905 Freckles == POJ 2560 最小生成樹(shù)
法一：Prim算法；法二：并查集實(shí)現(xiàn)Kruskar算法求最小生成樹(shù)
JOJ 1966 Super Market III == PKU 1456 Supermarket 帶限制的作業(yè)排序問(wèn)題（貪心+并查集）
提高題目：
POJ 2912 Rochambeau
POJ 1733 Parity game
POJ 1308 Is It A Tree?