温习以下解决方体的思路：
分析问题并找到解决问题的方案，将解决方案分成多个api。
则要解决的问题就变成了实现api。
（如果某个api难以实现，可能还需要重新改变api。往往好的情况是，在改变api时，会得到比一开始更多的有用的信息）
quick-find & quick-union
quick-find中：每次执行union(p,q)操作时，都要遍历整个并查集数组，将所有与p的标识符相同的结点的标识符都改为q。这样会导致每次调用union都要迭代整个数组，会很慢。 换来的是每次调用find会很快。
quick-union中：这种算法更像是一个树的结构，将结点一个连着一个直到根节点。
public void union(int p, int q) {// add connections between p and q
int pId = find(p);
int qId = find(q);
if (pId != qId) {
// this.a[q]=p;//ever fault. This way,we will lose the connection of q and a[q]
// of before
a[qId] = pId;
--N;
StdOut.printf("connecting %d and %d ... \n", p, q);
} else {
StdOut.printf("%d and %d has been connected!\n", p, q);
}
}
union操作：检测两个site（如，p和q）是否连接，如果不连接，则将这两个点进行连接。理所当然，与这两个点连接的点也产生了连接。我写的第一个版本，就犯了一个错误：仅仅时将p连接q，这样仅仅将p与q（以及连接q的site）连接到了一起，而没有将与p连接的site也连接进来。
改进版本则是将p的根节点连接q：
public void union(int p,int q){//add connections between p and q
if(!connected(p, q)){
//this.a[q]=p;//ever fault. This way,we will lose the connection of q and a[q] of before
int x=this.find(q);
a[x]=p;
--N;
StdOut.printf("connecting %d and %d ... \n",p,q);
}else{
StdOut.printf("%d and %d has been connected!\n",p,q);
}
}
并查集又称为并查树，即同属于同一个components的元素，顺着路径最终会到达同一个site。然而，若每次union直接将两棵并查树连接在一起（不考虑各子树的尺寸），则可能会出现一种极端低效的情况：即所有的的结点都依次连接在同一个根节点上。 此时每次的并查复杂度为O(N)（一共N个结点） 。
为避免这种情况，使用quick-union的改进算法：weighted-quick-union
增加一个size数组记录每个并查树的尺寸（结点个数）,保证每次都是将小树连接到大叔。这样一来，N个结点的并查树的最大结点深度不会超过log2N；
public void union(int p, int q) {// add connections between p and q
int pId = find(p);
int qId = find(q);
if(size[pId]<size[qId]){
a[pId]=qId;
size[qId]++;
}else{
a[qId]=pId;
size[pId]++;
}
--N;
}
证明：
两棵并查树连接，比较小的树的所有结点的结点深度会增加1（大的树的结点深度皆不变），因此这里追踪小树的某一个结点x.
设小树的结点数为N，则x的深度每增加1，则总体树的大小至少为N=N*2；
若最终的并查数结点数为N，则可得此时深度增加了log2N；
ps:也可以使用数学归纳法来证明。
weight-quick-union算法使得并查树更趋扁平化（树的结点深度增长速度为logN）
find()访问数组的此时为log2N
而union操作需要调用两次find
这些基本操作都是基于并查树的深度，所有这样一来，并查算法的效率就被大大提高了。
还有办法进一步改进吗？
有。压缩路径
在find方法中添加一个循环：使得要找的结点到该结点的根节点之间的所有结点都连接到根节点
实现：
public int find(int p){
int prep=p;
while(a[p]!=p){
p=a[p];
}
/*
path compressoin:to flatten the trees by make each node along the way link directly to the root of corresponding tree
extra cost:increased the complexity of extra logN;
*/
while(a[prep]!=prep){
a[prep]=p;
prep=a[prep];
}
return p;
}
这样可以使得并查树变得更加扁平化。
带来的时间开销是多少呢？每一次find操作从logN变成了2logN。这又是一次很值得的算法改进。
算法性能实验
现在读取有625个数据的site结点对（即总共要执行625次连接操作）
要统计的数据：每次连接操作对数组的访问次数accessed，数组的当前平均访问次数t/total（t为当前的连接操作数，total为当前的总访问数组次数）
开始：
首先是quick-find
实验代码：
int N=StdIn.readInt();
QuickFind uf=new QuickFind(N);
int t=1;//record the number of time of connection.
StdDraw.setXscale(0,N);
StdDraw.setYscale(0,2*N+10);
StdDraw.setPenRadius(.005);
while(!StdIn.isEmpty()){
int p=StdIn.readInt();
int q=StdIn.readInt();
if(!uf.connected(p, q)){
StdOut.printf("connecting %d and %d ... \n",p,q);
uf.union(p,q);
}else{
StdOut.printf("%d and %d has been connected!\n",p,q);
}
StdDraw.setPenColor(Color.DARK_GRAY);
StdDraw.point(t, uf.accessed);
StdOut.println("current accessed is"+uf.accessed);
StdDraw.setPenColor(Color.red);
StdDraw.point(t,uf.total/t);
++t;
}
得到实验图像（横轴为当前执行的连接操作数，纵轴的黑色，红色分别为本次连接访问数组次数和平均访问数组次数）
qucik-union
