1.問題描述：
有N個對象，對象間可以連通馋没。假設有一個命令用來連接兩個對象昔逗，將兩個對象傳入該命令就會連接兩者，還有一個命令來查詢任意兩個對象之間是否有連通的路徑存在（間接相連也算）篷朵。以上即：合并命令勾怒、查找命令婆排。
- 連接是個等價關系，滿足傳遞性笔链、自反性段只、對稱性等。
- 連通分量：相互連接的對象的最大集合鉴扫，連通分量重的任意兩個對象都是相連接的赞枕。
2.快速查找算法：
2.1算法描述（貪心）：
維護一個簡單的對象索引整數(shù)數(shù)組，相互連通的對象對應的數(shù)組值相等坪创，不連通的不相等鹦赎。
- 查找：如果p和q對應的數(shù)組值相同則它們倆連通。
- 連通：將兩組索引id轉為一致误堡。
圖片
??效率：初始化O(n)古话，并O(n)，查O(1)锁施。如果要在n個對象上進行n次合并操作陪踩，則是O(n2)，很不合理悉抵。
2.2代碼實現(xiàn)：
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的父節(jié)點姥饰。
- 查找就是找p和q是否有同一祖先節(jié)點傻谁。
- 合并p和q就是將p的祖先節(jié)點置為q的祖先節(jié)點，反之亦可列粪。
圖片
??初始化O(n)审磁，并O(n)，查O(n)岂座。如果樹特別高态蒂，則查特別耗時。
3.2代碼實現(xiàn)：
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算法描述：
我們要避免得到很高的樹费什，當一顆大樹和一顆小樹合并钾恢，避免將大樹放到小樹下面（這樣會使樹變高）。
用加權實現(xiàn)鸳址，權重是每棵樹中對象的個數(shù)瘩蚪。通過確保將小樹的根節(jié)點作為大樹的根節(jié)點的子節(jié)點以維持平衡。
初始化O(n)稿黍，并O(logn) 疹瘦，查O(logn)，因為任意節(jié)點X的深度最多是logn闻察。
4.2快速合并算法改進算法代碼實現(xiàn)：
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算法描述：
使用路徑壓縮的加權算法拱礁，即當我們經(jīng)過”遞推”找到祖先節(jié)點后，”回溯”的時候順便將它的子孫節(jié)點都直接指向祖先辕漂，這樣以后再次查時復雜度就變成O(1)了呢灶，再回溯一次將樹展平。這是最優(yōu)算法钉嘹。
初始化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); } } } }
