并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint
Sets）的合并及查询问题。
有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构：
- Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union：将两个子集合并成同一个集合。
下面代码实现一些并查集中的一些基本操作：
一、并查集的初始化
假设现在有一个全集合为S= {0,1,2,3,4,5,6,7,8,9} ，初始化时，将每一元素都划分成为一个单元素的集合。
如下图所示：
这样就初始化出10个单元素集合，每一个集合元素的parent值都是-1.
代码实现过程：
int parent[100];
//构造一个初始并查集，s是集合元素的个数，此时初始化了s个集合，每一个集合都只有一个元素
//数组的范围为parent[0]~parent[s-1]
//初始的时候，数组元素的值都是 -1，表示此时都是根结点。
void ufset(int s)
{
int si=s;
for(int i=0;i<si;i++)
parent[i]=-1;
}
二、合并Union
所谓合并，即是将两个不相交的集合合并成为一个集合，这个过程将一个集合的parent修改成另一集合的parent。
代码实现过程：
//集合的合并
//让root2的父指针指向root1即可实现两个集合的合并
void Union(int root2,int root1)
{
parent[root1]+=parent[root2];
parent[root2]=root1;
}
举个例子：初始化10个元素（如上图所示），进行下面的合并过程：
ufset(10); //初始化10个元素
Union(6,0);
Union(7,0);
Union(8,0);
Union(4,1);
Union(9,1);
Union(3,2);
Union(5,2);
合并之后的结果：
但是进行这种合并之后，可能会出现一种不好的效果。如下图：
我们称之为一棵退化的树。
那么如何进行改进呢？我们可以使用加权规则进行合并。也就是将集合元素少的归到集合元素多的中去。
例如：
下面给出代码实现：（注意下面这个方法存在错误，请看下面第二个方法，已修正错误。）
//使用加权规则得到改进的Union操作
void WeightUnion(int root2,int root1)
{
int r2=Find(root2); //r2和r1是root2和root1的父结点
int r1=Find(root1);
int temp;
if(r1!=r2)
{
temp=parent[r1]+parent[r2];
if(parent[r1]<parent[r2]){parent[r1]=temp;parent[r2]=r1;} //以r2根的树结点多
else {parent[r1]=r2;parent[r2]=temp;}
}
}
错误提醒：很感谢某位网友指出我上面段代码的错误，由于一时疏忽上面WeightUnion这个方法有点错误！修改如下：
//使用加权规则得到改进的Union操作
void WeightUnion(int root2,int root1)
{
int r2=Find(root2); //r2和r1是root2和root1的父结点
int r1=Find(root1);
int temp;
temp=parent[r1]+parent[r2];
if(parent[r1]<=parent[r2])
{
parent[r1]=temp; //以r2根的树结点多
parent[r2]=r1;
}
else
{
parent[r1]=r2;
parent[r2]=temp;
}
}
三、查找Find
我们知道，只有当查找到的元素的parent值为负数（此时集合元素个数用这个负数表示），才表示找到根。
//查找元素x所在集合
//从x开始，沿父指针链一直向上，直到向上，直到达到一个父指针域为负值的结点位置
int Find(int x) //迭代查找方式
{
while(parent[x]>=0) x=parent[x];
return x;
}
/*
int find_1(int x) //递归查找方式
{
if(parent[x]<0) return x; //x是根时，直接返回x
else return find_1(parent[x]); //否则，递归找x的父的根
}
*/
进一步优化，在查找过程中可以采用折叠规则压缩路径。
实现的代码：
//折叠规则压缩路径法
//包含元素i的树中搜索根，并将从元素i到根的路径上的所有结点都变成根的结点
int collapsingfind(int i)
{
int j;
for(j=i;parent[j]>=0;j=parent[j]); //搜索j的根
while(i!=j) //向上逐次压缩
{
int temp=parent[i];
parent[i]=j;
i=temp;
}
return j; //返回根
}
附：上面代码的完整版：
#include <iostream>
using namespace std;
int parent[100];
//构造一个初始并查集，s是集合元素的个数，此时初始化了s个集合，每一个集合都只有一个元素
//数组的范围为parent[0]~parent[s-1]
//初始的时候，数组元素的值都是 -1，表示此时都是根结点。
void ufset(int s)
{
int si=s;
for(int i=0;i<si;i++)
parent[i]=-1;
}
//查找元素x所在集合
//从x开始，沿父指针链一直向上，直到向上，直到达到一个父指针域为负值的结点位置
int Find(int x) //迭代查找方式
{
while(parent[x]>=0) x=parent[x];
return x;
}
/*
int find_1(int x) //递归查找方式
{
if(parent[x]<0) return x; //x是根时，直接返回x
else return find_1(parent[x]); //否则，递归找x的父的根
}
*/
//折叠规则压缩路径法
//包含元素i的树中搜索根，并将从元素i到根的路径上的所有结点都变成根的结点
int collapsingfind(int i)
{
int j;
for(j=i;parent[j]>=0;j=parent[j]); //搜索j的根
while(i!=j) //向上逐次压缩
{
int temp=parent[i];
parent[i]=j;
i=temp;
}
return j; //返回根
}
//集合的合并
//让root2的父指针指向root1即可实现两个集合的合并
void Union(int root2,int root1)
{
parent[root1]+=parent[root2];
parent[root2]=root1;
}
//使用加权规则得到改进的Union操作
void WeightUnion(int root2,int root1)
{
int r2=Find(root2); //r2和r1是root2和root1的父结点
int r1=Find(root1);
int temp;
if(r1!=r2)
{
temp=parent[r1]+parent[r2];
if(parent[r1]<parent[r2]){parent[r1]=temp;parent[r2]=r1;} //以r2根的树结点多
else {parent[r1]=r2;parent[r2]=temp;}
}
}
int main()
{
ufset(10); //初始化10个元素
Union(6,0);
Union(7,0);
Union(8,0);
Union(4,1);
Union(9,1);
Union(3,2);
Union(5,2);
for(int i=0;i<10;i++) cout<<parent[i]<<" ";
return 0;
}