1.问题描述：

有N个对象，对象间可以连通。假设有一个命令用来连接两个对象，将两个对象传入该命令就会连接两者，还有一个命令来查询任意两个对象之间是否有连通的路径存在（间接相连也算）。以上即：合并命令、查找命令。

• 连接是个等价关系，满足传递性、自反性、对称性等。
• 连通分量：相互连接的对象的最大集合，连通分量重的任意两个对象都是相连接的。

2.快速查找算法：

2.1算法描述（贪心）：

维护一个简单的对象索引整数数组，相互连通的对象对应的数组值相等，不连通的不相等。

• 查找：如果p和q对应的数组值相同则它们俩连通。
• 连通：将两组索引id转为一致。

图片
  效率：初始化O(n)，并O(n)，查O(1)。如果要在n个对象上进行n次合并操作，则是O(n2)，很不合理。

2.2代码实现：

public class UF{ private int[] id; UF(int N){ //构造器 id = new int[N]; for(int i = 0;i < N;i++) id[i] = i; } void union(int p,int q){//并 int pid = id[p]; int qid = id[q]; for(int i = 0;i < id.length;i ++) if(id[i] == pid) id[i] = qid; } boolean connected(int p,int q){//查 return id[p] == id[q]; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } } }

3.快速合并算法

3.1算法描述：

运用了懒计算的思路，维护一棵树，id[i]记录着i的父节点。

• 查找就是找p和q是否有同一祖先节点。
• 合并p和q就是将p的祖先节点置为q的祖先节点，反之亦可。

图片
  初始化O(n)，并O(n)，查O(n)。如果树特别高，则查特别耗时。

3.2代码实现：

public class UF{ private int[] id; UF(int N){ //构造器 id = new int[N]; for(int i = 0;i < N;i++) id[i] = i; } void union(int p,int q){//并 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; id[p] = q; } boolean connected(int p,int q){//查 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; return p == q; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } } }

4.快速合并算法改进算法1：

4.1算法描述：

我们要避免得到很高的树，当一颗大树和一颗小树合并，避免将大树放到小树下面（这样会使树变高）。

用加权实现，权重是每棵树中对象的个数。通过确保将小树的根节点作为大树的根节点的子节点以维持平衡。

初始化O(n)，并O(logn) ，查O(logn)，因为任意节点X的深度最多是logn。

4.2快速合并算法改进算法代码实现：

public class UF{ private int[] id; UF(int N){ //构造器 id = new int[N]; sz = new int[N]; for(int i = 0;i < N;i++) id[i] = i; sz = 1; } void union(int p,int q){//并 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; if(p == 1) return; if(sz[p] < sz[q]) {id[p] = q;sz[p]+= sz[q];} else {id[q] = p;sz[q]+= sz[p];} } boolean connected(int p,int q){//查 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; return p == q; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } } }

5.快速合并算法改进算法2：

5.1算法描述：

使用路径压缩的加权算法，即当我们经过”递推”找到祖先节点后，”回溯”的时候顺便将它的子孙节点都直接指向祖先，这样以后再次查时复杂度就变成O(1)了，再回溯一次将树展平。这是最优算法。

初始化O(n)，并和查都非常接近但是仍没达到1（均摊成本）。

5.2算法代码：

public class UF{ private int[] id; UF(int N){ //构造器 id = new int[N]; sz = new int[N]; for(int i = 0;i < N;i++) id[i] = i; sz = 1; } void union(int p,int q){//并 while(p != id[p]){ id[p] = id[id[p]]; p = id[p] } while(q != id[q]){ id[q] = id[id[q]]; q = id[q]; } if(p == 1) return; if(sz[p] < sz[q]) {id[p] = q;sz[p]+= sz[q];} else {id[q] = p;sz[q]+= sz[p];} } boolean connected(int p,int q){//查 while(p != id[p]){ id[p] = id[id[p]]; p = id[p]; } while(q != id[q]){ id[q] = id[id[q]]; q = id[q]; } return p == q; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } } }