public class UnionFind1 implements UF {
private int[] id; // 我們的第一版Union-Find本質(zhì)就是一個(gè)數(shù)組
public UnionFind1(int size) {
id = new int[size];
// 初始化, 每一個(gè)id[i]指向自己, 沒(méi)有合并的元素
for (int i = 0; i < size; i++)
id[i] = i;
}
@Override
public int getSize(){
return id.length;
}
}
查詢 - 快速查詢 O(1)
快速查詢的時(shí)間復(fù)雜度是 O(1)津畸；
在數(shù)組中查詢索引為 p 的元素的值（索引為 p 的元素所屬的集合的編號(hào)）的時(shí)間復(fù)雜度是 O(1)；
查詢兩個(gè)元素 p 和 q 所在的集合是否是同一個(gè)必怜，時(shí)間復(fù)雜度也是O(1)肉拓；
// 查找元素p所對(duì)應(yīng)的集合編號(hào)
// O(1)復(fù)雜度
private int find(int p) {
if(p < 0 || p >= id.length)
throw new IllegalArgumentException("p is out of bound.");
return id[p];
}
// 查看元素p和元素q是否所屬一個(gè)集合
// O(1)復(fù)雜度
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
合并 - 將 p 和 q 所在的集合合并成一個(gè)集合 O(n)
先查看 p 和 q 所在的集合是否是同一個(gè)集合；
如果是同一個(gè)集合梳庆，則無(wú)需合并暖途；
如果不是同一個(gè)集合卑惜，將 p 所在集合的元素的集合值，全部改為 q 所在的集合的集合值驻售；
