Algorithms

UnionFind.java

//QuickUnion algorithm to solve the dynamic connectivity problem, not optimal
public class QuickUnion {
    private int[] id;

    public QuickUnion(int n){
        id = new int[n];
        for(int i = 0; i < n; ++i)
            id[i] = i;
    }
    public int getRoot(int n){
        while(id[n] != n)
            n = id[n];
        return n;
    }
    public void merge(int a, int b){
        int rootA = getRoot(a);
        int rootB = getRoot(b);

        if(a != b)
            id[rootA] = rootB;
    }
    public boolean isConnected(int a, int b){
        return getRoot(a) == getRoot(b);
    }
}

public class Main {

    public static void main(final String[] args){
        QuickUnion qu = new QuickUnion(10);

        qu.merge(4, 3);
        qu.merge(3, 8);
        qu.merge(6, 5);
        qu.merge(9, 4);
        qu.merge(2, 1);

        System.out.println(qu.isConnected(8, 9));
        System.out.println(qu.isConnected(8, 4));
        System.out.println(qu.isConnected(5, 4));

        qu.merge(5, 0);
        qu.merge(7, 2);
        qu.merge(6, 1);
        qu.merge(7, 3);

        System.out.println(qu.isConnected(5, 4));
    }
}