并查集

-并查集的基本操作

---

并查集的操作
并查集是一种简单的集合表示，它支持一下三种操作：
1.Union(S,Root1,Root2)：把集合S中的子集合Root2并入子集合Root1中。要求Root1和Root2互不相交，否则不执行合并。
2.Find(S,x)：查找集合S中单元素x所在的子集合，并返回该子集合的名字。
3.Initial(S)：将集合S中每一个元素都初始化为只有一个单元素的子集合。

通常用树（森林）的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的树，存放在双亲表示数组内。通常用数组元素的下标代表元素名，根结点的下标代表子集合名，根结点的双亲结点为负数。

---

为了得到两个子集合的并，只要将其中一个子集合根结点的双亲之争指向另一个集合的根结点即可。
在采用树的双亲指针表示作为并查集的存储表示时，集合元素编号从0到size-1，其中size是最大元素的个数

---

//并查集的结构定义
#define SIZE 100
int UFSets[SIZE];            //集合元素数组（双亲指针数组）

//并查集的初始化操作
void Initial(int S[]){
	for(int i=0;i<size;i++)        //每个自成单元素集合
		S[i]=-1;
}

//Find操作（函数在并查集S中查找并返回包含元素x的树的根）
Int Find(int S[],int x){
	while(S[x]>=0)         //循环查找x的根
		x=S[x];
	return x;
}

//Union操作(函数求两个不相交子集合的并集)
void Union(int S[],int Root1,int Root2){
	//要求Root1与Root2是不同的，且表示子集合的名字
	S[Root2]=Root1;
}

---