《算法导论3rd第二十一章》用于不相交集合的数据结构

如果现在有需：求从n个不同结点的中，提取不相交集合，如何处理。

不相关：即A集合的数据和B集合没关系。放在连通图里面，则表示两个集合中的点相互不可达

这里我们要使用不相交集合的数据结构，不相交集合上有两个重要操作

1. 找出给定的元素所属的集合
2. 合并两个集合。

不相交集合教据结构维护一组不相交的动态集合的集合S={S1， S2, …, SK}。每个集合通过一个代表来识别，代表是集合中的某个成员

• 在某些应用中，哪一个成员被选作代表是无所谓的，但是必须保证在两次寻找某一集合的代表两次，得到的答案应该是相同的。
• 在另一些应用中，关于如何选择代表可能存在着预先说明的规则，例如选择集合中的最小元素(当然假定集合中的元素是可以排序的)。

集合中的每一个元素是由一个对象表示。设x表示一个对象，希望支持以下操作：

1. MAKE-SET(x)：建立一个新的集合，其唯一成员(因而其代表)就是x。因为各集合是不相交的，故x不会出现在其他集合中。
2. UNIOn(x，y)：将包含x和y的动态集合Sx和Sy合并为一个新的集合(即这两个集合的并集)。在经过此操作后，原来的集合Sx和 Sy需要从总集合S中删除。
3. FIND-SET(x)：返回一个指针，指向包含x的(唯一)集合的代表。

如下图，确定一个无向图中连通子图。

求联通子图代码如下，计算过程见上图：

V[G]表示结点，E[G]表示边， CONNECTED-COMPONENTS对图形进行预处理，然后SAME-COMPONENT回答两个顶点是否在同一个连通分量。

如下图，每个集合用一个自己的链表来表示。链表中的每个对象包含一个指向链表中下一个对象的指针和一个指回到集合对象的指针。

在链表的实现方法中，

1. MAKE-SET操作需要O(1)的时间，只需要创造一个只有x对象的新的链表即可。
2. FIND-SET需要O(1)的时间，仅沿着x对象的返回指针返回到集合对象
3. UNIOn(x，y)，花费的时间与y所在的链表长度呈线性关系

为了降低UNIOn的复杂度，使用一种加权合并启发式策略：可以总是把较短的表拼接到较长的表中。

在不相交集合的另一种更快的实现中，用有根树来表示集合。每棵树的根包含了集合的代表，并且是它自己的父结点。如下图：

虽然采用了这种表示的算法并不比采用链表表示的算法更快，但是，通过引人两种启发式策略：“按秩合并”和“路径压缩”。

• 按秩合并：用秩表示结点高度的一个上界。在按秩合井中。具有较小秩的根在UNIOn操作中要指向具有较大秩的根。
• 路径压缩：在FIND-SET操作中，利用这种启发式策略，来使查找路径上的每个结点都直接指向根结点。路径压缩并不改变结点的秩。

其代码如下

1. MAKE-SET创建了一个单元素集合时，对应的树中唯一结点的初始秩为0
2. MAKE-SET创建了一个单元素集合时，对应的树中唯一结点的初始秩为0
3. 执行完FIND-SET操作后，查找路径上每个结点都直接指向了根

《数据结构与算法——并查集(不相交集合)》
《Data Structures for Disjoint Sets》