Weighted Quick Union Find - Dynamic connectivity with path compression

UnionFind.java

static class UnionFind {
    int[] id;
    int[] sz;
    int count;

    public UnionFind(int N) {
        this.count = N;
        this.id = new int[N];
        this.sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    public int find(int p) {
        if(id[p]==p) return p;        
        return (id[p]=find(id[p]));
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    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] = id[j];
            sz[j] += sz[i];
        } else {
            id[j] = id[i];
            sz[i] += sz[j];
        }
        count--;
    }

    public int noOfComponents() {
        return count;
    }
}