并查集
并查集（Union-Find Set），也称为不相交集数据结构（Disjointed Set Data Structure）。是指一系不相交的集合（Sets），提供合并（Union）和查找(Find)两种操作。
- find（I）
find(i)即查找I所归属的集合，通常我们使用find(i)和find(j)判断i和j是否连通，即是否属于同一个集合 - union(int i , int j)
顾名思义，union方法即将I和J所在的两个集合连通起来，执行这个方法后，I所在集合和所有元素和J所在集合的所有元素都连通
适用场景
Union-Find算法最常见的使用场景就是动态连通（dynamic-connectivity）了
我们在浩如烟海的数据中要判断两个元素是否连通，是很有实际意义的。比如计算机网络中两台不同计算机是否连通，社交网络中两个人是否有联系，一张图片中两个像素之间的联系等。
Quick Find
我们首先来看一下第一种实现方案。数据结构我们用数据来实现，假设一个集合有N个元素，我们用一个长度为N的数组来存储。array[0]...array[N-1]。相同集合内的元素，array中的元素相等。
public class QuickFindUF
{
private int[] id;
public QuickFindUF(int N){
id = new int[N];
for(int j = 0 ; j < N ; j ++){ //N array accesses
id[j] = j;
}
}
public boolean connected(int p , int q){
return id[p] == id[q]; //2 array accesses
}
public void union(int p , int q){ //at most 2N + 2 array accesses
int pid = id[p];
int qid = id[q];
for(int i = 0 ; i < id.length ; i ++){
if(id[i] == pid) id[i] = qid;
}
}
}
我们看到，quick-find算法find是很快的，时间复杂度只有1, 但是union操作相当耗时，quick-find算法的时间度是N的平方。这就意味着，当处理大量数据时，耗时指数上升。换个说法，假设计算机能力提高十位，而我们的数据量扩大十倍，我们的速度反而降低了十倍。
Quick-Union
我们再来看一下另一种实现-Quick-Union算法。数据结构我们保持不变，依然是一个数组，但数据中的元素不再是"groupId"。我们逻辑上把这个数据想象成一棵树，而数据中的元素存放的是父节点。
这种情况下，假设我们要计算union(p , q)，只需要将p所在树的根节点设置成q所在树的根节点即可，话不多说，上图。
quick-union顾名思义，是快速union的算法，与quick-find相比，不需要遍历数组，将所有集合中元素都修改为新的"groupId"。而只需要将两个集合的根节点连接到一起即可。我们看下代码：
public class QuickUnionUf{
private int[] id;
public QuickUnionUf(int N){
id = new int[N];
for(int j = 0 ; j < N ; j ++){ //N array accesses
id[j] = j;
}
}
private int root(int p){ //depth of p array accesses
while(id[p] != p){
p = id[p];
}
return p;
}
public boolean connected(int p , int q){
return root(id[p]) == root(id[q]); //depth of p and q array accesses
}
public void union(int p , int q){ //depth of p and q array accesses
int i = root(p);
int j = root(q);
id[I] = j;
}
}
weighted-quickUnion
以上两种算法复度度都不够好，我们再看下如何改进。quick-union我们已经分析过了，相比于quick-find，通过树的根节点的改变，减少了union的时间复杂度。但是在极端情况下，树可能会出现不平衡的状况，最坏情况时间复杂度为N。我们的思路是要尽量使树平衡，因为平衡树深搜的复杂度是lgN，所以我们优化了quick-union。
public class weightedQuickUnionUF{
private int[] id;
private int[] sz;
private int count;
public WeightedQuickUnionUF(int N){
count = N;
id = new int[N];
for(int i=0; i<N; i++) id[i] = I;
sz = new int[N];
for(int i=0; i<N; i++) id[i] = 1;
}
public int count(){
return count;
}
public boolean connected(int p, int q){
return find(p) == find(q);
}
private int root(int p){
while( p != id[p]) p = id[p];
return p;
}
public void union(int p, int q){
int i = root(p);
int j = root(q);
if( i == j) return;
//判断两棵树大小，将小树挂在大树上
if( sz[i] < sz[j]) { id[i] = j; sz[j] += sz[I];}
else { id[j] = i; sz[i] += sz[j]; }
count--;
}
}
path-compression
这样就结束了吗？还有没有什么优化的点？随着数据的增加，树的深度不断增加，性能会逐渐变差。这个时候，如果我们在计算一个node的root时，将node为根的树摘下来，挂在当前树的根结点上，会降低树的深度，也就是提高效率，降低时间复杂度。这种方法叫路径压缩：path-compression。
要做这个修改其实很简单，我们只需要修改一下root方法，就可以了。
private int root(int p){
while( p != id[p]) {
id[p] = id[id[p]]; //加了这一句，当循环结束后，就会把p为根结点的树摘下来，挂在所在树的根结点上
p = id[p];
}
return p;
}
