本文主要是介绍ProblemSet of Union Find，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
并查集模板：
快速查找 并查集
这是一个eager的并查集，就是在合并两个节点的时候将这两个节点的组份id修改成同一个根节点的编号.
public class QuickFindUF {private int[] componentID; //各个节点（数组索引）所属的组份（数组值）private int count; // number of componentspublic QuickFindUF(int n){if(n<0) throw new IllegalArgumentException();this.count=n;this.componentID=new int[n];for(int i=0;i<n;i++){componentID[i]=i;}}//连接两个节点 O(n)public void union(int p,int q){int rootP=this.find(p);int rootQ=this.find(q);if(rootP==rootQ)return;int label=Math.min(rootP, rootQ);int max=Math.max(rootP, rootQ);for(int i=0;i<this.componentID.length;i++)if(this.componentID[i]==max)this.componentID[i]=label;count--;}//在查找p节点所属组份ID过程中会将实际上同属于一个组份的不同ID修改成相同public int find(int p){int n=this.componentID.length;if(p<0||p>=n)throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));while(p!=this.componentID[p]){this.componentID[p]=componentID[componentID[p]];p=componentID[p];}return p;}public boolean isConnected(int p,int q){int n=this.componentID.length;if(p<0 || p>=n || q<0 || q>=n)throw new IllegalArgumentException("index " + p +" or "+q+ " is not between 0 and " + (n-1));return this.find(p)==this.find(q);}public int count(){return this.count;}
}
快速合并 并查集
public class QuickUnionUF {private int[] componentID;private int count; // number of componentspublic QuickUnionUF(int n){if(n<0) throw new IllegalArgumentException();this.count=n;this.componentID=new int[n];for(int i=0;i<n;i++){componentID[i]=i;}}//连接两个节点void union(int p,int q) //O(N){int rootP=this.find(p);int rootQ=this.find(q);if(rootP==rootQ)return;this.componentID[rootP]=rootQ;count--;}//在查找p节点所属组份ID过程中会将实际上同属于一个组份的不同ID修改成相同int find(int p) //O(N){int n=this.componentID.length;if(p<0||p>=n)throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));while(p!=this.componentID[p]){this.componentID[p]=componentID[componentID[p]];p=componentID[p];}return p;}boolean isConnected(int p,int q) //O(N){int n=this.componentID.length;if(p<0 || p>=n || q<0 || q>=n)throw new IllegalArgumentException("index " + p +" or "+q+ " is not between 0 and " + (n-1));return this.find(p)==this.find(q);}int count(){return this.count;}
加权快速合并 并查集
public class WeightedQuickUnionUF {/** 加权快速合并并查集在快速合并并查集基础上：把 深度较小的树合并到较大的树上*/int[] componentID;int[] size; //以下标i为根节点的节点数int count; // number of componentspublic WeightedQuickUnionUF(int n) //O(N){if(n<0) throw new IllegalArgumentException();this.count=n;this.componentID=new int[n];this.size=new int[n]; //以索引i为根节点的树的总结点数for(int i=0;i<n;i++){componentID[i]=i;this.size[i]=1;}}//连接两个节点void union(int p,int q) //O(1){int rootP=this.find(p);int rootQ=this.find(q);if(rootP==rootQ)return;if(this.size[rootP]<=this.size[rootQ]){this.size[rootQ]+=this.size[rootP];this.componentID[rootP]=rootQ;}else{this.size[rootP]+=this.size[rootQ];this.componentID[rootQ]=rootP;}count--;}//在查找p节点所属组份ID过程中会将实际上同属于一个组份的不同ID修改成相同int find(int p) //O(N),O(the depth of p) if given root nodes{int n=this.componentID.length;if(p<0||p>=n)throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));while(p!=this.componentID[p]){this.componentID[p]=componentID[componentID[p]];p=componentID[p];}return p;}boolean isConnected(int p,int q){int n=this.componentID.length;if(p<0 || p>=n || q<0 || q>=n)throw new IllegalArgumentException("index " + p +" or "+q+ " is not between 0 and " + (n-1));return this.find(p)==this.find(q);}int count(){return this.count;}
}
加权路径压缩快速合并 并查集
public class WeightedQuickUnionPathCompressionUF {int[] father;int[] size;int count; // number of componentspublic WeightedQuickUnionPathCompressionUF(int n) //O(N){if(n<0) throw new IllegalArgumentException();this.count=n;this.father=new int[n];this.size=new int[n]; //以索引i为根节点的树的总结点数for(int i=0;i<n;i++){father[i]=i;this.size[i]=1;}}//连接两个节点boolean union(int p,int q) //O(1){int rootP=this.find(p);int rootQ=this.find(q);if(rootP==rootQ)return false;if(this.size[rootP]<=this.size[rootQ]){this.size[rootQ]+=this.size[rootP];this.father[rootP]=rootQ;}else{this.size[rootP]+=this.size[rootQ];this.father[rootQ]=rootP;}count--;return true;}//在查找p节点所属组份ID过程中会将实际上同属于一个组份的不同ID修改成相同int find(int p) //O(N),O(the depth of p) if given root nodes{int n=this.father.length;if(p<0||p>=n)throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));int root=p;while(root!=this.father[root])root=this.father[root];while(p!=root){int new_root=this.father[p];this.father[p]=root;p=new_root;}return p;}boolean isConnected(int p,int q){int n=this.father.length;if(p<0 || p>=n || q<0 || q>=n)throw new IllegalArgumentException("index " + p +" or "+q+ " is not between 0 and " + (n-1));return this.find(p)==this.find(q);}int count(){return this.count;}
684. Redundant Connection
class Solution {public static int maxCount=1010;public int[] findRedundantConnection(int[][] edges) {WeightedQuickUnionPathCompressionUF uf=new WeightedQuickUnionPathCompressionUF(maxCount);for(int[] e:edges){if(!uf.union(e[0],e[1]))return e;}return new int[]{0,0};}
}public class WeightedQuickUnionPathCompressionUF {int[] father;int[] size;int count; // number of componentspublic WeightedQuickUnionPathCompressionUF(int n) //O(N){if(n<0) throw new IllegalArgumentException();this.count=n;this.father=new int[n];this.size=new int[n]; //以索引i为根节点的树的总结点数for(int i=0;i<n;i++){father[i]=i;this.size[i]=1;}}//连接两个节点boolean union(int p,int q) //O(1){int rootP=this.find(p);int rootQ=this.find(q);if(rootP==rootQ)return false;if(this.size[rootP]<=this.size[rootQ]){this.size[rootQ]+=this.size[rootP];this.father[rootP]=rootQ;}else{this.size[rootP]+=this.size[rootQ];this.father[rootQ]=rootP;}count--;return true;}//在查找p节点所属组份ID过程中会将实际上同属于一个组份的不同ID修改成相同int find(int p) //O(N),O(the depth of p) if given root nodes{int n=this.father.length;if(p<0||p>=n)throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));int root=p;while(root!=this.father[root])root=this.father[root];while(p!=root){int new_root=this.father[p];this.father[p]=root;p=new_root;}return p;}boolean isConnected(int p,int q){int n=this.father.length;if(p<0 || p>=n || q<0 || q>=n)throw new IllegalArgumentException("index " + p +" or "+q+ " is not between 0 and " + (n-1));return this.find(p)==this.find(q);}int count(){return this.count;}
}
[外交]
package ShunFeng;import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;public class Main1 {public static void main(String[] args) {Scanner cin = new Scanner(System.in);int n = cin.nextInt(); // 参会人数int m = cin.nextInt(); // 语言数量int k = cin.nextInt(); // 记录条数HashMap<Integer, ArrayList<Integer>> record = new HashMap<>();for (int i = 0; i < k; i++) {int a = cin.nextInt(), b = cin.nextInt();if (record.containsKey(b)) {record.get(b).add(a);} else {ArrayList<Integer> tmp = new ArrayList<>();tmp.add(a);record.put(b, tmp);}}QuickUnionUF uf = new QuickUnionUF(n); //建立大小为n的并查集，不会任何语言的人或者只会一种语言（并且该语言不被其他任何人掌握的）始终独立为一个组份for (int i : record.keySet()) {ArrayList<Integer> arr = record.get(i);int a = arr.get(0);for (int j = 1; j < arr.size(); j++) {uf.union(a-1, arr.get(j)-1); //人的编号减一对应数组下标的范围}}System.out.println(uf.count()-1);/*7 4 91 12 13 14 23 24 35 36 33 41->(1,2,3)2->(4,3)3->(4,5,6)4->(3)3 3 22 33 1*/}
}public class QuickUnionUF {private int[] componentID;private int count; // number of componentspublic QuickUnionUF(int n){if(n<0) throw new IllegalArgumentException();this.count=n;this.componentID=new int[n];for(int i=0;i<n;i++){componentID[i]=i;}}//连接两个节点void union(int p,int q) //O(N){int rootP=this.find(p);int rootQ=this.find(q);if(rootP==rootQ)return;this.componentID[rootP]=rootQ;count--;}//在查找p节点所属组份ID过程中会将实际上同属于一个组份的不同ID修改成相同int find(int p) //O(N){int n=this.componentID.length;if(p<0||p>=n)throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));while(p!=this.componentID[p]){this.componentID[p]=componentID[componentID[p]];p=componentID[p];}return p;}boolean isConnected(int p,int q) //O(N){int n=this.componentID.length;if(p<0 || p>=n || q<0 || q>=n)throw new IllegalArgumentException("index " + p +" or "+q+ " is not between 0 and " + (n-1));return this.find(p)==this.find(q);}int count() //返回组份数{return this.count;}
}
这篇关于ProblemSet of Union Find的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
