Union-find approach - quick-union

• The data structure for this approach is as follows:
  • integer array id[N]
    • N is equal to the number of objects in the disjoint set
      • each index of id[] corresponds to an object in the disjoint set
  • interpretation: id[i] is parent of i
  • root of i is id[id[id[...id[i]...]]]

id[10]{0, 1, 9, 4, 9, 6, 6, 7, 8, 9}

// root of `3` is `9` (`id[3]` is `4`, `id[4]` is `9`)

• Find:
  • Check if p and q have the same root
• Union:
  • To merge components containing p and q, set the id of p’s root to the id of q’s root

Example implementation

public class QuickUnionUF
{
  private int[] id;
  
  public QuickUnionUF(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 connected(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;
  }
}

Problem: too slow

• trees can get very tall
• for each connected() (Find) operation, the array can be accessed as many as N times

Cost:

• new: N
• Union: N (including cost of finding roots)
• Find: N