Quick Find Algorithm

This algorithm can be used to solve dynamic connectivity problem. This algorithm is kept very simple. It supports two operations,

·         connected(a, b) check if a and b are in the same component

·         union(a, b) if two elements are not in the same component then this operation merge these components(merge(component of a, component of b))

Data-Structure

This algorithm uses a simple array id[] to maintain each element's component.

connected(a, b)

Return true if both are in the same component. It just checks id[a] and id[b] are equal or not. It takes constant time O(1).

union(a, b)

This operation first checks if a and b are already in the same component. If a and b are in different component, then union merge these two component. Here every elements of the component containing a is replaced by the component of b. It takes linear time O(Number of nodes).

Here is the JAVA Implementation of this algorithm.

package quickfinduf;

/**
 *
 * @author imdad
 */
public class QuickFindUF {

    private int[] id;

    public QuickFindUF(int N) {
        id = new int[N];

        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }

    public boolean connected(int a, int b) {
        return id[a] == id[b];
    }

    public void union(int a, int b) {
        System.out.println("union(" + a + "," + b + ")");//union operation of a and b
        printID();//id[] before union operation

        if (!connected(a, b)) {
            int aid = id[a];
            int bid = id[b];

            for (int i = 0; i < id.length; i++) {
                if (id[i] == aid) {
                    id[i] = bid;
                }
            }
        }
        printID();//id[] changed after union operation
    }

    private void printID() {//Method to see state of  datastructure id[]
        System.out.print(id[0]);
        for (int i = 1; i < id.length; i++) {
            System.out.print(" " + id[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {

        QuickFindUF obj = new QuickFindUF(10);

        obj.union(4, 3);
        //obj.printID();

        obj.union(3, 8);
        obj.union(6, 5);
        obj.union(9, 4);
        obj.union(2, 1);

        System.out.println(obj.connected(8, 9) ?
                "8 and 9 are connected" :
                "8 and 9 are not connected");
        System.out.println(obj.connected(5, 0) ? 
                "5 and 0 are connected" : 
                "5 and 0 are not connected");

        obj.union(5, 0);
        obj.union(7, 2);
        obj.union(6, 1);



    }
}

Complexity

Initialization 
Initialization will take O(N) operations(Array initialization) where N is the number of component.
Union
Each union operation will take heist O(N) time, Here N is the component size of the first parameter of union() operation. 
Connected 
It will take constant time O(1).

So, Quick-Union  Algorithm is a Quadratic O(N^2) time algorithm.