1.Quick found

Data structure.

• Integer array id[] of size N.
• Interpretation: p and q are connected if they have the same id.

Find

Check if p and q have the same id.

Time complexity: O(1)

Union

To merge components containing p and q, change all entries with id[p] to id[q].

Time complexity: O(N)

public class QuickFind{
   private int[] id;
}  
public QuickFind(int N){
    id = new int[N];
    for (int i = 0; i < N; i++)
      id[i] = I;   //set id of each object to itself
}
public boolean find(int p, int q){
    return id[p] == id[q];
}
public void union(int p, int q){
    int pid = id[p];
    for (int i = 0; i < id.length; i++)
        if (id[i] == pid) id[i] = id[q];
    }
}

2.Quick Union

Data structure.

• Integer array id[] of size N.
• Interpretation: id[i] is parent of i.
• Root of i is id[id[id[...id[i]...]]].

Find

Check if p and q have the same root.

Time complexity: O(N)

Union

Set the id of q's root to the id of p's root.

Time complexity: O(N*)

In theory it should be less than quick find because we don't need to go through the entire list.

public class QuickUnion
{
    private int[] id;
    public QuickUnion(int N){
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = I;
    }
    private int root(int i){
        while (i != id[i]) i = id[I];
        return I;
    }
    public boolean find(int p, int q){
        return root(p) == root(q);
    }
    public void union(int p, int q){
       int i = root(p);
       int j = root(q);
       id[i] = j;
    }
}

3.Weighted Quick Union

Data structure.

• Almost identical to quick-union.
• Maintain extra array sz[] to count number of elements in the tree rooted at i.

Find

Check if p and q have the same root.

Time complexity: O(logN)

Union

• merge smaller tree into larger tree
• update the sz[] array.

Time complexity: O(logN*)

...
if(size[i]<size[j]){
id[i]=j;
size[j]+=size[i];
}else {
id[j]=i;
size[i]+=size[j];
}

...

4.Weighted Quick Union with path compression

Path compression. Just after computing the root of i, set the id of each examined node to root(i).

Standard implementation: add second loop to root() to set the id of each examined node to the root.

Simpler one-pass variant: make every other node in path point to its grandparent.

Data structure: Using Path compression

Find

The same as QU Time complexity: O(N+MlogN*)

Union

The same as QU Time complexity: O(N+MlogN*)

public int root(int i){
    while(i!=id[i]){
        id[i]=id[id[i]];
        i=id[i];
    }
    return i;
}