首页 > 代码库 > 并查集
并查集
1、quick-find 算法
import java.util.Scanner ;public class UF{ private int[] id ; private int count ; public UF(int N){ count = N ; id = new int[N] ; for (int i=0;i<N;i++) { id[i] = i ; } } public int count(){ return count ; } public boolean connected(int p, int q){ return find(p) == find(q) ; } public int find(int p){ return id[p] ; } public void union(int p, int q){ int pID = id[p] ; int qID = id[q] ; if (pID == qID) { return ; }else{ for (int i=0;i<id.length;i++) { if(id[i]==pID){ id[i] = qID ; } } count-- ; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in) ; System.out.println("please input the number of nodes:") ; int N = sc.nextInt() ; UF uf = new UF(N) ; System.out.println("please input the number of relateon of nodes:") ; int m = sc.nextInt() ; for(int i=0;i<m;i++){ int p = sc.nextInt() ; int q = sc.nextInt() ; if(uf.connected(p,q)){ continue ; }else{ uf.union(p,q) ; //System.out.println(p + " " + q) ; } } System.out.println(uf.count() + " components.") ; }}
2、quick-union 算法
import java.util.Scanner ;public class UF02{ private int[] id ; private int count ; public UF02(int N){ count = N ; id = new int[N] ; for (int i=0;i<N;i++) { id[i] = i ; } } public int count(){ return count ; } public boolean connected(int p, int q){ return find02(p) == find02(q) ; } public int find02(int p){ while(p!=id[p]){ p = id[p] ; } return p ; } public void union02(int p, int q){ int pRoot = find02(p) ; int qRoot = find02(q) ; if (pRoot == qRoot) { return ; }else{ id[pRoot] = qRoot ; count-- ; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in) ; System.out.println("please input the number of nodes:") ; int N = sc.nextInt() ; UF02 uf = new UF02(N) ; System.out.println("please input the number of relateon of nodes:") ; int m = sc.nextInt() ; for(int i=0;i<m;i++){ int p = sc.nextInt() ; int q = sc.nextInt() ; if(uf.connected(p,q)){ continue ; }else{ uf.union02(p,q) ; //System.out.println(p + " " + q) ; } } System.out.println(uf.count() + " components.") ; }}
3、加权 quick-union 算法
import java.util.Scanner ;public class UF03{ private int[] id ; private int[] sz ; private int count ; public UF03(int N){ count = N ; id = new int[N] ; sz = new int[N] ; for (int i=0;i<N;i++) { id[i] = i ; sz[i] = 1 ; } } public int count(){ return count ; } public boolean connected(int p, int q){ return find03(p) == find03(q) ; } public int find03(int p){ while(p!=id[p]){ p = id[p] ; } return p ; } public void union03(int p, int q){ int pRoot = find03(p) ; int qRoot = find03(q) ; if (pRoot == qRoot) { return ; }else{ if (sz[pRoot]<sz[qRoot]) { id[pRoot] = qRoot ; sz[qRoot] += sz[pRoot] ; }else{ id[qRoot] = pRoot ; sz[pRoot] += sz[qRoot] ; } count-- ; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in) ; System.out.println("please input the number of nodes:") ; int N = sc.nextInt() ; UF03 uf = new UF03(N) ; System.out.println("please input the number of relateon of nodes:") ; int m = sc.nextInt() ; for(int i=0;i<m;i++){ int p = sc.nextInt() ; int q = sc.nextInt() ; if(uf.connected(p,q)){ continue ; }else{ uf.union03(p,q) ; //System.out.println(p + " " + q) ; } } System.out.println(uf.count() + " components.") ; }}
并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。