1. 集合表示：

集合运算：交、并、补、差，判定一个元素是否属于某一集合

并查集：集合并、查某元素属于什么集合

并查集问题中集合存储如何实现？

可以用树结构表示集合，树的每个节点代表一个集合元素

例子：有10台电脑{1, 2, 3,...,9, 10},已知下列电脑之间已经实现了连接：

1和2、2和4、3和5、4和7、5和8、6和9、6和10

问：2和7之间、5和9之间是否是连通的？

解决思路：

1) 将10台电脑看成10个集合{1}, {2}, {3},..., {9}, {10}

2) 已知一种连接"x和y"，就将x和y对应的集合合并；

3) 查询"x和y是否是连通的"就是判别x和y是否属于同一集合

2. 采用数组存储形式：

3. 集合运算：

1) 查找某个元素所在的集合（用根结点表示）

int Find(SetType S[], ElementType x)
{
	/*在数组S中查找值为X的元素所属的集合*/
	/*MaxSize是全局变量，为数组S的最大长度*/
	
	int i;
	for(i = 0; i< MaxSize && S[i].Data != X; i++);
	if(i >= MaxSize)
	{
		return -1;
	}
	for(;S[i].Parent >= 0; i = S[i].Parent);
	return i;/*找到X所属集合，返回树根结点在数组S中的下标*/
}

a) 分别找到X1和X2两个元素所在集合树的根结点

b) 如果他们不同根，则将其中一个根结点的父结点指针设置成另一个根结点的数组下标。

<pre name="code" class="cpp">void Union(SetType S[], ElementType X1, ElementType X2){
	int Root1, Root2;
	Root1 = Find(S, X1);
	Root2 = Find(S, X2);
	if(Root1 != Root2)
	{
		S[Root2].Parent = Root1;//当X1和X2不属于同一子集时，才需要合并
	}
}

如果一直采用合并的过程，有可能树就会不平衡，因此采用如下改进：