一、不相交集合的操作
一个不相交集合数据结构(disjoint-set data structure)维护了一个不相交动态集的集合S={S1, S2,…，Sk}。我们用一个代表(representative)来标识每个集合， 它是这个集合的某个成
员。
这个数据结构支持一下三个操作：
MAKE-SET(x):建立一个新的集合，代表为x，因为不相交集合，因此别的集合中没有x。
UNION(x,y):将包含x和y两个动态集合合并成一个新的集合，代表可以是其中任何一个元素，同时我们要将两个合并前的集合删除，避免相交；实际上，我们一般会将另一个集合中的元素并到这个集合中。
FIND-SET(x):返回一个指针，这个指针包含x（唯一）集合的代表。
1、一个应用
CONNEXTED-COMPONENTS
//将v放到自己的集合中
for each vextex v ∈ G.V
MAKE-SET(v)
//对包含u和v的集合进行合并
for each edge(u,v) ∈ G.E
if FIND-SET(u) != FIND-SET(v)
UNION(u,v)
SAME-COMPONENT(u,v)
//u和v边是否在同一个集合中
if FIND-SET(u) == FIND-SET(v)
return TRUE
else return FALSE
2、不相交集合的链表表示
每个集合用一个自己的链表来表示。每个集合的对象包含head属性和tail属性，head属性指向表的第一个对象，tail属性指向表的最后一个对象。链表中的每个对象都包含一个集合成员、一个指向链表中下一个对象的指针和一个指回到集合对象的指针。在每个链表中，对象可以以任意的次序出现。代表是链表中第一个对象的集合成员。
MAKE-SET(x)：只需要创建一个只有x对象的新的链表。
FIND-SET(x)：沿着x对象的返回指针返回到集合对象，然后返回head指向对象的成员。
1、合并的一个简单实现
上图将y所在的链表合并到了x所在的链表。我们通过x.tail迅速找到拼接y所在的链表的位置，这时候要删除y所在链表中所有的对象，因此，必须更新指向集合对象的指针，比如上图中bceh对象的指针都被更新。
2、一种加权合并的启发式策略
可以假设每个表中还包含了表的长度，以及拼接次序可以任意的话，我们总是将较短的表拼接到较长的表中。