Api：
public class UF{
UF(int N);//初始化N個觸點
void union(int p,int q) //在p和q之間添加一條連接
int find(int p) // p所在的分量的標識符
boolean connected(intp ,int q)//如果q和p在同一各分量中則返回true
int count()//聯(lián)通分量的數(shù)量
}
加權(quán)quick-union算法：
將小數(shù)的根節(jié)點連接到大樹的根節(jié)點
public class WeightedQuickUnionUF{
private int[] id;
private int[] sz;
private int count;
public WeightedQuickUnionUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
sz = new int[N];
for (int i = 0; i < N; i++) sz[i] = 1;
}
public int getCount() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
while (p != id[p]) p = id[p];
return p;
}
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
count--;
}
}
最優(yōu)解法：路徑壓縮的加權(quán)quick-union算法
要實現(xiàn)路徑壓縮矢腻，只需要為find()添加一個循環(huán)，將在路徑上遇到的所有節(jié)點都直接鏈接到根節(jié)點岔冀。
public int find(int p) {
int root = p;
while (root != id[root]) root = id[root];
while (p!=root) {
int next = id[p];
id[p] = root;
p = next;
}
return root;
}
