Quick Find
数组的每个位置存相应的节点id，相连接的节点的位置存相同的id。
判断是否相连（connected）只需判断两位置的id是否相同。
而将两节点连接起来（union）则需要将第一个节点的id下所有的节点都更改为第二个节点的id。
public class QuickFind{
private int[] id;
public QuickFind(int N){
id = new int[N];
for(int i = 0;i < N;i++){
id[i] = i;
}
}
//判断是否相连
public boolean connected(int p,int q){
return id[p]==id[q];
}
//将两点相连
public void union(int p,int q){
int pid = id[p];
int qid = id[q];
if(pid == qid){
return;
}
for(int i = 0;i<id.length;i++){
if(id[i] == pid){
id[i] = qid;
}
}
}
}
在上述程序中，查找（connected）的时间复杂度为O(1)，而union和initialize的时间复杂度均为O(N)。
Quick Union
数组的每个位置存的是其父节点；
判断两个节点是否相连（connected）需判断两节点是否有相同的根节点。
将两个节点连接（union）则只需将第一个节点的根节点作为第二个节点根节点的孩子即可。
public class QuickFind{
private int[] id;
public QuickFind(int N){
id = new int[N];
for(int i = 0;i < N;i++){
id[i] = i;
}
}
//找根节点
public int root(int q){
while(id[q] != q){
q = id[q];
}
return q;
}
//判断是否相连
public boolean connected(int p,int q){
return root(p)==root(q);
}
//将两点相连
public void union(int p,int q){
id[root(p)] = root(q);
}
}
由于查找和归并都需要找根节点，因此这里面所有的方法时间复杂度都为O(N)。
Quick-Union Improvements
由于quick union中可能会碰到tall tree，那么寻找其根节点就是一个很耗时的工作。
改进算法中应用了 weighted algorithm，也就是在连接的时候每次将较小的tree连到较大的tree上，避免让较大的tree在某个tree的底部从而使这个tree变得很长。
此时需要另一个数组sz存储每个tree的大小。
public class QuickFind{
private int[] id;
private int[] sz;
public QuickFind(int N){
id = new int[N];
sz = new int[N];
for(int i = 0;i < N;i++){
id[i] = i;
sz[i] = 1;
}
}
//找根节点
public int root(int q){
while(id[q] != q){
q = id[q];
}
return q;
}
//判断是否相连
public boolean connected(int p,int q){
return root(p)==root(q);
}
//将两点相连
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{
idj] = i;
sz[i]+=sz[j];
}
}
}
拥有N个节点的树的最大深度为logN。因此此方法中connected和union的时间复杂度应为O(logN)
更进一步的改进：path compression
在搜索根节点时会走过路径上的所有点，莫不如将路径上的所有点都直接加到根节点上。为了时间复杂度的效率及代码的简洁性，考虑将路径上的每一个节点加到其祖父节点（grandparent）下。
public int root(int q){
while(id[q] != q){
id[q] = id[id[q]];//将该节点加到其祖父节点下
q = id[q];
}
return q;
}
http://visualgo.net/ufds 展示的为最后path compression的做法（搜索根节点时将路径上每个结点加到根节点上）。
