并查集
QuickUnion
class QuickUnion {
Integer[] arr;
public QuickUnion(int size) {
this.arr = new Integer[size];
for (int i = 1; i < arr.length; i++)
arr[i] = new Integer(i);
}
public int findRoot(int i) {
while (i != arr[i]) i = arr[i];
return i;
}
public void union(int a, int b) {
a = findRoot(a);
b = findRoot(b);
arr[a] = b;
}
}
加权QucikUnion
class QuickUnion {
private int[] arr;
private int[] sz;
public QuickUnion(int size) {
this.arr = new int[size];
this.sz = new int[size];
for (int i = 0; i < arr.length; i++){
arr[i] = i;
sz[i] = 1;
}
}
public int findRoot(int i) {
int count = 0;
while (i != arr[i]) {
i = arr[i];
count++;
}
System.out.println("访问次数:"+count);
return i;
}
public void union(int a, int b) {
a = findRoot(a);
System.out.println("内容:"+a);
b = findRoot(b);
System.out.println("内容:"+b);
if (a == b) return;
if (sz[a] > sz[b]) {
arr[b] = a;
sz[a] += sz[b];
} else {
arr[a] = b;
sz[b] += sz[a];
}
}
}
Loading...