简单并查集
public class UnionFind {
private int[] id;
private int count;
public UnionFind(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;
}
public int getCount() {
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 pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
for(int i = 0; i < id.length; i++)
if(id[i] == pRoot) id[i] = qRoot;
count--;
}
}
快速并查集
public class QuickUnion {
private int[] id;
private int count;
public QuickUnion(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;
}
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 pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
}
加权快速并查集
public class WeightedQuickUnion {
private int[] id;
private int count;
private int[] sz;
public WeightedQuickUnion(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 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 pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
if(sz[pRoot] < sz[qRoot]) { id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; }
else { id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; }
count--;
}
路径压缩的加权快速并查集
public class PathCompressionWeightedQuickUnion {
private int[] id;
private int count;
private int[] sz;
public PathCompressionWeightedQuickUnion(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 getCount() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
if (p != id[p]) id[p] = find(id[p]);
return id[p];
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
if(sz[pRoot] < sz[qRoot]) { id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; }
else { id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; }
count--;
}
}
复杂度对比
存在N伙强盗增长数量级(最坏情况)
算法 构造函数 union() find()
union-find算法 O(n) O(n) O(1)
quick-union算法 O(n) 树的高度 树的高度
加权quick-union算法 O(n) O(lgn) O(lgn)
路径压缩的加权quick-union算法 O(n) 非常接近O(1) 非常接近O(1)
理想情况 O(n) O(1) O(1)
