并查集：(union-find sets)是一種簡單的用途廣泛的集合. 并查集是若干個不相交集合，能夠?qū)崿F(xiàn)較快的合并和判斷元素所在集合的操作，應(yīng)用很多，如其求無向圖的連通分量個數(shù)、最小公共祖先、帶限制的作業(yè)排序，還有最完美的應(yīng)用：實現(xiàn)Kruskar算法求最小生成樹。
一般采取樹形結(jié)構(gòu)來存儲并查集，在合并操作時可以利用樹的節(jié)點數(shù)(加權(quán)規(guī)則)或者利用一個rank數(shù)組來存儲集合的深度下界--啟發(fā)式函數(shù)，在查找操作時進行路徑壓縮使后續(xù)的查找操作加速。這樣優(yōu)化實現(xiàn)的并查集，空間復(fù)雜度為O(N)，建立一個集合的時間復(fù)雜度為O(1)，N次合并M查找的時間復(fù)雜度為O(M Alpha(N))，這里Alpha是Ackerman函數(shù)的某個反函數(shù)，在很大的范圍內(nèi)這個函數(shù)的值可以看成是不大于4的，所以并查集的操作可以看作是線性的。
它支持以下三種操作:
－Union (Root1, Root2) //合并操作；把子集合Root2和子集合Root1合并.要求：Root1和 Root2互不相交,否則不執(zhí)行操作.
－Root(x) //搜索操作；搜索元素x所在的集合,并返回該集合的名字--根節(jié)點.
－MakeSet (N) //構(gòu)造函數(shù)。將并查集中s個元素初始化為s個只有一個單元素的子集合.
－對于并查集來說，每個集合用一棵樹表示。
－集合中每個元素的元素名分別存放在樹的結(jié)點中，此外，樹的每一個結(jié)點還有一個指向其雙親結(jié)點的指針。
－為簡化討論，忽略實際的集合名，僅用表示集合的樹的根來標(biāo)識集合。
Union分為兩個版本，Union1是將parent域充分利用，其中Parent為正數(shù)時表示該節(jié)點的父節(jié)點下標(biāo)，為負數(shù)時表示該節(jié)點為一個根節(jié)點，其絕對值為該集合包含的節(jié)點總數(shù)。 Union2版本是將rank利用，保存樹的高度。
Del1 是狹義上的刪除操作。(一次刪除后不再使用) Del2是廣義上的刪除操作，利用了一個Mapping數(shù)組來保存映射信息
當(dāng)使用Del2的時候， 各個函數(shù)的調(diào)用方式是：Union1(Mapping[a],Mapping[b]);MakeSet(N) 如果顯式調(diào)用Root，也需要Mapping[x]; Root(Mapping[x]);
綜上，一般不涉及刪除操作，使用的是MakeSet(N) Root(x) Union1()
如果涉及刪除操作，使用的是MakeSet(N) Root(Mapping[x]) Union1(Mapping[x],Mapping[y]) ,Del2[x]; //注意這里是Del[x];
reshape()來統(tǒng)計各個并查集分量塊，當(dāng)操作都進行完了之后，才進行統(tǒng)計的！
Sosi實現(xiàn)：應(yīng)用的版本不同。。
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 500001
struct
{
int parent; //標(biāo)記父節(jié)點，如果parent為負數(shù)則表示是父節(jié)點，負數(shù)的絕對值表示此塊內(nèi)節(jié)點數(shù)目
int rank; //rank 為樹高
bool flag; //標(biāo)記是否被刪除 0 未被刪除，1 被刪除 如果引入刪除操作，rank樹高性質(zhì)被破壞
}UFS[MAXN]; //UnionFindSet UFS
int Mapping[MAXN]; //映射數(shù)組，為了進行刪除元素。
vector<int> UFSSet[MAXN];
int Dmax;
//其中Parent為正數(shù)時表示該節(jié)點的父節(jié)點下標(biāo)，為負數(shù)時表示該節(jié)點為一個根節(jié)點，其絕對值為該集合包含的節(jié)點總數(shù)。
//rank表示權(quán)值，在不同問題中有不同的含義。
void MakeSet(int N) /* 初始化 */
{
for(int i=0;i<N;i++) //0-indexed
{
UFS[i].parent=-1; /* 開始每個節(jié)點單獨構(gòu)成一個集合 */
UFS[i].rank=0; /* 權(quán)值視具體情況付初值 */
UFS[i].flag=0;
Mapping[i]=i;
}
}
int Root(int x) /* 查找包含接點x的集合的根節(jié)點 */
{
int i=x,temp;
while(UFS[i].parent>=0)
i=UFS[i].parent;
while(i!=x) /* 壓縮路徑以提高以后檢索效率 */
{
temp=UFS[x].parent;
UFS[x].parent=i; //直接將x的祖先命為根節(jié)點
x=temp; //繼續(xù)處理x的原祖先
}
return i;
}
/*
Union1 的優(yōu)點是能把并查集數(shù)某顆樹的節(jié)點數(shù)找到，在parent域中
且rank域空缺，可以去掉
如果使用，可以賦給rank域額外信息
*/
void Union1(int a,int b) /* 合并a和b所在的集合 */
{
int x,y;
x=Root(a);
y=Root(b);
if(x==y) return;
if(UFS[x].parent<UFS[y].parent)
UFS[x].parent+=UFS[y].parent,UFS[y].parent=x; /* 始終將較小樹作為較大樹的子樹 */
else
UFS[y].parent+=UFS[x].parent,UFS[x].parent=y;
}
/*
Union 2 的優(yōu)點是把樹高可以統(tǒng)計出來。。此時rank被占用
*/
void Union2(int a, int b) //將rank較大的作為父節(jié)點
{
int x = Root(a), y = Root(b);
if( x == y ) return ;
if( UFS[x].rank > UFS[y].rank ) UFS[y].parent = x;
else{
UFS[x].parent = y;
if( UFS[x].rank == UFS[y].rank ) UFS[y].rank++;
}
}
//此時的刪除只是狹義上的刪除，看1號節(jié)點被刪除之后，當(dāng)下一次被添加的時候是什么性質(zhì)了
//此時需要維護一個映射表！
//當(dāng)新來一個元素之后，我們首先都是先進行映射！Mapping[]將所有的標(biāo)號i修改成為Mapping[i];
//初始化Mapping為i；
void Del1(int x)
{
if(UFS[x].parent==-1) //獨立頂點
UFS[x].flag=true;
else
{
if(UFS[x].parent>=0) //葉子節(jié)點
{
UFS[x].flag=true;
int i=x;
while(UFS[i].parent>=0)
i=UFS[i].parent;
UFS[i].parent+=1;
}
else
UFS[x].parent+=1,UFS[x].flag=true; //并查集集合頂點
}
}
void Del2(int x)
{
int initialx=x; //便于修改一開始的x
if(UFS[x].flag==true) //已被刪除
x=Mapping[x];
if(UFS[x].parent==-1) //獨立頂點
UFS[x].flag=true;
else
{
if(UFS[x].parent>=0) //葉子節(jié)點
{
UFS[x].flag=true;
int i=x;
while(UFS[i].parent>=0)
i=UFS[i].parent;
UFS[i].parent+=1;
}
else
UFS[x].parent+=1,UFS[x].flag=true; //并查集集合頂點
}
Mapping[initialx]=Dmax;
Mapping[Dmax]=Dmax;
UFS[Dmax].parent=-1;
UFS[Dmax].rank=0;
UFS[Dmax].flag=0;
Dmax++;
}
void reshape()
{
//我們默認此處存儲為0-indexed
int UFSBlock=0;
for(int i=0;i<Dmax;i++)
{
if(UFS[i].parent<-1||((UFS[i].parent==-1) && (UFS[i].flag==0))) //如果一個節(jié)點被刪除
{
UFSBlock++;
UFSSet[0].push_back(i);
}
}
for(int i=0;i<Dmax;i++)
{
if(UFS[i].flag==0) //i號節(jié)點未被刪除
{
int x=Root(i); //找到i號根節(jié)點
for(int j=0;j<UFSSet[0].size();j++) //根節(jié)點編號
{
if(x==UFSSet[0][j])
{
UFSSet[j+1].push_back(i);
break;
}
}
}
}
cout<<" 索引編號：";
for(int i=0;i<UFSSet[0].size();i++)
cout<<UFSSet[0][i]<<" ";
cout<<endl;
for(int i=1;i<=UFSBlock;i++)
{
cout<<" BLOCK "<<i<<endl;
for(int j=0;j<UFSSet[i].size();j++)
{
cout<<UFSSet[i][j]<<" ";
}
cout<<endl;
}
cout<<"UFSBlock Num "<<UFSBlock<<endl;
}
/*
1 如果涉及到刪除操作，那么各個函數(shù)的調(diào)用方式是：
Union(Mapping[a],Mapping[b]);
MakeSet(N)
如果顯式調(diào)用Root，也需要Mapping[x]; Root(Mapping[x]);
*/
int main()
{
int N=7; //7個點
MakeSet(N);
Dmax=N;
Union1(Mapping[1],Mapping[0]);
Union1(Mapping[1],Mapping[2]);
Union1(Mapping[3],Mapping[4]);
Union1(Mapping[1],Mapping[4]);
Del2(0);
Del2(5);
Del2(0);
Del2(0);
Union2(Mapping[0],Mapping[5]);
for(int i=0;i<Dmax;i++)
{
if(UFS[i].flag==1)
{
cout<<"Index"<<i<<" be deleted"<<endl;
cout<<"Index "<<i<<" parent "<<UFS[i].parent<<" rank "<<UFS[i].flag<<endl;
}
else
cout<<"Index "<<i<<" parent "<<UFS[i].parent<<" rank "<<UFS[i].flag<<endl;
}
reshape();
return 0;
}