public class QuickFindUF {
private int[] id;
// O(N)
public QuickFindUF(int x) {
id = new int[N];
for (int i=0; i<x; i++) {
id[i] = i;
}
}
// O(N)
public void Union(int p, int q) {
if (!FindQuery(p, q)) {
int idp = id[p];
id[p] = id[q];
for (int i=0; id<id.length; i++) {
if (id[i] == idp) {
id[i] = id[q];
}
}
}
}
// O(1)
public boolean FindQuery(int p, int q) {
return id[p] ==id[q];
}
}
Quick Union[lazy approach]
public class QuickUnion {
// id[i] represents the root of i
private int[] id;
// O(N)
public QuickUnion(int N) {
id = new int[N];
for (int i=0; i<N; i++) {
id[i] = i;
}
}
// O(N)
public Union(int p, int q) {
int rootp = root(p);
int rootq = root(q);
id[rootp] = rootq;
}
// worst case: O(N)
private int root(int x) {
while (id[x] != x) x = id[x];
return x;
}
// O(N)
public boolean Find(int p, int q) {
return root(p) == root(q);
}
}
Improvements
WeightedQU
private int[] sz;
// O(lgN)
public Union(int p, int q) {
int rootp = root(p);
int rootq = root(q);
if (sz[rootp] >= sz[rootq]) {
id[rootq] = rootp;
sz[rootp] += sz[rootq];
} else {
id[rootp] = rootq;
sz[rootq] += sz[rootp];
}
}
Path Compression
// O(lgN)
private int root(int x) {
while (id[x] != x) {
id[x] = id[id[x]];
x = id[x];
}
return x;
}
