public class QuickUnion implements DisjointSets{
    private int[] parent;

    /* O(N) */
    public QuickUnion(int N){
        parent = new int[N];
        for (int i = 0; i < N; i++){
            parent[i] = i;
        }
    }

    private int findRoot(int p){
        /* Add Path Compression:
        tie all nodes passed through to the ROOT
        => iterated log scale lg* N
        Implementation: Using Recursion !!! recursive up and down !!! */
        int nodeParent = parent[p];
        if (p == parent[p]){
            return p;
        } else {
            parent[p] = findRoot(parent[p]);
            return parent[p];
        }
    }

    /* need to iterate through the array ! => O(N) */
    public void connect(int p, int q){
        int pRoot = findRoot(p);
        int qRoot = findRoot(q);
        parent[qRoot] = pRoot;
        return;
    }

    /* very fast */
    public boolean isConnected(int p, int q){
        return (findRoot(p) == findRoot(q));
    }

    public static void main(String[] args) {
        QuickUnion qf = new QuickUnion(10);
        qf.connect(1, 2);
        qf.connect(1, 3);
        qf.connect(2, 4);
        qf.connect(0, 3);
        System.out.println(qf.isConnected(0, 4));
        System.out.println(qf.isConnected(3, 6));
    }
}


public interface DisjointSets {

    void connect(int p, int q);

    boolean isConnected(int p, int q);
}