希望大家通過本次的學習後，
能夠加深對數組的了解和使用
import java.util.Random;
public class UnionFind {
public static int count = 0 ;
private int[] parent ;
private int[] rank ;
public UnionFind(int size) {
parent = new int[size] ;
rank = new int[size] ;
for(int i = 0 ;i < parent.length ; i ++) {
parent[i] = i ;
rank[i] = 1 ;
}
}
public int find(int p) {
while(p != parent[p]) {
parent[p] = parent[parent[p]] ;
p = parent[p] ;
}
return p ;
}
public int getSize() {
return parent.length ;
}
public boolean isConnected(int p , int q) {
return find(p) == find(q) ;
}
public void unionElements(int p , int q) {
//在查找時進行的路徑壓縮
int pRoot = find(p) ;
int qRoot = find(q) ;
if(rank[pRoot] > rank[qRoot]) {
parent[qRoot] = pRoot ;
}else if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot ;
}else {
parent[pRoot] = qRoot ;
rank[qRoot] += 1 ;
}
}
private static double testUF(UnionFind uf , int m ) {
int size = uf.getSize() ;
Random random = new Random() ;
long startTime = System.nanoTime() ;
for(int i = 0 ; i < m ; i ++) {
int a = random.nextInt(size) ;
int b = random.nextInt(size) ;
uf.unionElements(a , b) ;
}
for(int i = 0 ; i < m ;i ++) {
int a = random.nextInt(size) ;
int b = random.nextInt(size) ;
if(uf.isConnected(a, b) ) {
count ++ ;
}
}
System.out.println("連接配接次數：" + count);
long endTime = System.nanoTime() ;
return (endTime - startTime) / 1000000000.0 ;
}
public static void main(String[] args) {
int size = 100000 ;
int m = 1000000 ;
UnionFind uf = new UnionFind(size) ;
System.out.println("UnionFind : " + testUF(uf , m) + "s");
}
}
