并查集，在一些有N个元素的应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。
首先我们给出并查集（union-find）的api：
在《algorithm》书中，对与uf的应用直接给出了代码，但是其中find和union方法并没有直接实现，而是空着的。书中代码如下：
注意：这里看见有一个StdIn的类作为类似于输入流的作用，这个在java中是不存在的，这是这本书自己构造的一个类。相信以后在这本书中也会有类似的部分，可以在网上找到其中的具体实施代码，我会发送出来的。
为什么不直接实现find和union方法呢，这里会考虑到数据结构和算法复杂度的问题。
我们将其分为：quickunion，quickfind，weightedquickunion，weightedquickunion with path compression；
1）Quick-Find
其中判断p和q两个元素是否连接便是让两个元素的id[]相同。
此时，find（）便是直接返回id[p]的值
而union（）便是将连接的两个集合的id[]变为一致：当然，我们首先要判断她们是不是已经连接；
由上图便可看出，我们union（3，4），得到两者的id[]相同，即id[3]=id[4]=3（id值为连接的集合包含的任意一个数）；
得到的代码如下：
package unionFind;public class QuickFindUF { private int id[]; private int count; public QuickFindUF(int N){ count=N; id=new int[N]; for(int i=0;i
2)Quick-Union
Quick-Union的结构如下图所示：
即每一个结点的id为上一个结点。而根节点便是root=id[root]；
判断两个元素是否连接则是判断两个元素的根（root）是否相同。
find（）则为找到元素的根节点；
union（p，q）即将p的根节点与q的根节点连接。
代码实现如下：
package unionFind;public class QuickUnionUF { private int id[]; private int count; public QuickUnionUF(int N){ id=new int[N]; count=N; for(int i=0;i
3）Weighted Quick-Union
当然，我们如果胡乱的将根节点相互连接，会导致这个树的结构非常糟糕，比如：
我们可以看到这个树的结构非常非常糟糕。
为了避免这个情况，我们记录树的大小，并且总是将小的树连接到大的树：
使用这种方法可以很大程度的优化树的结构，例如上图的树我们可以变为：
具体实现代码如下：
package unionFind;public class WeightedQuickUnionUF { private int id[]; private int count; private int sz[]; public WeightedQuickUnionUF(int N){ count=N; id=new int[N]; sz=new int[N]; for(int i=0;i
4）Weighted Quick-Union with Path Compression
最优情况下，我们希望所有的节点都直接连接到根节点上，但是又不希望像QuickUnion那样大量修改连接，这时，我们可以在检查节点的同时将它与根节点直接连接。
例如，我们对下列并查集进行union（7，3）；
在采取最优算法下，结果如下：
可以看出，我们将遍历到的节点都直接与根节点直接连接，这一切只需要在find内的循环进行修改就可以实现。
具体的代码如下：
package unionFind;public class WeightedQuickUnionUFWPC { private int id[]; private int count; private int sz[]; public WeightedQuickUnionUFWPC(int N){ count=N; id=new int[N]; sz=new int[N]; for(int i=0;i
这四种方法能够适应不同的情况，但是对于算法复杂度来说，这四种方法就会有很大的差别：
对于每一项的得出，《algorithm》给出了很详细的解释，我希望自己能够有时间写一篇文章来细讲一下。（别说了。感觉还有好多坑没填）