Problem:
Implement quick union find with 2 arrays.for example, give 10 vertex 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and 4 connections 0 -- 3, 3 -- 6, 6 -- 9, 4 -- 5
we got 6 connected components
{0, 3, 6, 9} {1}, {2}, {4, 5}, {7}, {8}
then:
isConnected(0, 6) should return true, isConnected(1, 5) should return false.
count() should return 6.
Solution:
//time O(N), space O(N)
public class UF {
private int[] id;
private int[] sz;
private int count;
public UF(int N) {
id = new int[N];
sz = new int[N];
for(int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1;
}
count = N;
}
public int find(int p) {
int root;
for(root = p; root != id[root]; root = id[root]);
while(p != root) {
int newp = id[p];
id[p] = root;
p = newp;
}
return root;
}
public void union(int p, int q) {
if(isConnected(p, q)) return;
int i = find(p);
int j = find(q);
if(sz[i] > sz[j]) {
id[j] = i;
sz[i] += sz[j];
} else {
id[i] = j;
sz[j] += sz[i];
}
count--;
}
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
public int count() {
return count;
}
public static void main(String[] args) {
UF uf = new UF(10);
for(int i = 0; i < 7; i=i+3) {
System.out.println(i + "--" + (i + 3));
uf.union(i, i + 3);
}
System.out.println(uf.isConnected(0, 9));
System.out.println(uf.isConnected(0, 2));
System.out.println(uf.count());
}
}
