数据结构-并查集

//并查集的定义 
int UFSets[Size];//j集合元素数组（双亲指针数组） 
//并查集初始化 
void initial(int s[])
{
	for (int i=0;i<Size;i++)
	{
		s[i]=-1;//每个自成单元素集合 
	}
 } 
//查找并查集中x的根 
int Find(int s[],int x)
{
	while(s[x]>=0)//循环寻找x的根 
	{
		x=s[x];
	}
	return x;//根的s[]小于0 
}
//查找并查集中x的根优化
//（压缩路径）先找到根节点，再将查找路径上所有的节点都挂在根节点的下面
int Find1(int s[],int x)
{
	int root=x;
	while(s[root]>=0)
	{
		root=s[root];
	}
	while(root!=x)//压缩路径 
	{
		int t=s[x];//保存原来的双亲节点 
		s[x]=root;//x挂到根节点的下面 
		x=t;
	}
	return root;
 } 
//求两个不相交子集的并集 
void Union(int s[],int root1,int root2)
{
	if(root1==root2) return;//属于同一个集合返回 
	s[root2]=root1;//将root2的根并到root1下面 
}
//求并集优化（尽量树小的并在树大的下面）
//根节点的并查集数值用负值的绝对值表示树的结点数 
void Union1(int s[],int root1,int root2)
{
	if(root1==root2) return ;
	if(s[root2]>s[root1])//root2的树小于root1的树 
	{	
		s[root1]+=s[root2];//将root2树中的节点数加到 root1中 
		s[root2]=root1;//将root2的根并到root1下面 
	}
	else{
		s[root2]+=s[roo1];//将root1树中的结点数加到root2中 
		s[root1]=root2;//将root1的根并到root2下面 
	}
 }