首页 > 代码库 > 并查集

并查集

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.") ;	}}

  

 

并查集