计算机算法学习(1) - 不相交集合数据结构

不相交集合 故名思意就是一种含有多个不相交集合的数据结构。典型的应用是确定无向图中连通子图的个数。其基本操作包括：

Make-Set(x):建立一个新的集合，集合的成员是x；

Union(x,y): 将包含x和y的集合合并为一个集合；

Find-Set(x): 返回指向包含x的集合的指针；

下面是一个例子，(a)是一个无向图，(b)是使用不相交集合来找连通子图的个数。做法是初始为各个顶点为一个集合，然后遍历各个边，把边的端点的集合进行合并，当处理完所有的边，能连通的顶点就在一个集合里了，这样就生成了4个集合。也就是有4个连通子图。

如何实现不相交集合呢？

最直观和简单的方法是用链表：每个集合是一个链表，合并时，就是把一个链表接到另一个链表的后面。由于需要支持Find-Set操作，所以，每个元素都需要有指针指向集合的头节点。更新链表也需要更新这个头指针，使其指向新集合的头。如果我们不考虑合并时两个集合的大小，那最坏情况下是把长的接到短的后面，这样就需要更新更多的头指针。而简单的优化方式就是总是把短的链表接到长的后面。

更好的方式是用有根树来表示。如果不做优化，有根树并不比链表快很多，但是使用按秩合并和路径压缩两种优化后，可以得到跟操作数量m成线性关系的运行时间。

按秩合并：基本思想是跟链表时的优化类似，当两个集合（树）要合并时，将小的集合并到大的里面。所采取的方法并不是记录集合的大小，而是用秩来描述，秩是集合树高度的一个上界。在Union时，两个要合并的集合x，y。如果x的秩大，那就把y并入x：将y的根的父节点设置为x的根，这时x的秩是不需要改变的，因为高度没有改变，只是增加了x的根的子节点的数量，但如何x和y的秩相同，那就随机把某个根的父节点设置为另一个的根，但这时需要把秩增加1.

路径压缩：路径压缩是说在Find-Set时，将查找路径上的每个节点都直接指向其根节点，也就是把树的高度变小了，根节点的孩子多了。但这些操作并不改变秩的大小。所以这里的秩只是一个模糊的上界，并不真的表示树的高度。 路径压缩的好处就是，在后续的Find-Set操作可以变快，下图中Find-Set(a)时把搜索路径上所有的节点的父节点都成了根节点，那后续的Find-Set(b)就可以一步完成了。

不相交集合的使用还是可以比较灵活的，遇到有环的问题，也许可以考虑，下面是勇幸|Thinking分享的一个题目：

A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0..N?1]. Sets S[K] for 0 ≤ K < N are defined as follows: S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }. Sets S[K] are finite for each K.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns the size of the largest set S[K] for this array. The function should return 0 if the array is empty.

这个问题也是比较适合用这个不相交集合这种数据结构来解决的。

原文：http://www.cnblogs.com/whyandinside/p/3889234.html