Union-find approach - quick-find

• 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
    • each value in id[] denotes the root/representative element of the set/component containing that particular object
  • interpretation: p and q are connected if and only if they have the same id

id[10]{0, 1, 1, 8, 8, 0, 0, 1, 8, 8}

// connected sets:
//  {0, 5, 6}
//  {1, 2, 7}
//  {3, 4, 8, 9}

• Find:
  • Check if p and q have the same id
• Union:
  • To merge components containing p and q, change all entries whose id == id[p] to id[q]

Example implementation

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 p, int q)
  {
    return id[p] == id[q];
  }
  
  public void union(int p, int q)
  {
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i < id.length; i++)
      if (id[i] == pid) id[i] = qid;
  }
}

Problem: too slow (algorithm is quadratic)

• for each new and union() operation, the array is accessed N times (the for loops)
  • we only use init() once, but union() is certainly too expensive:
    • N^2 array accesses are required to execute N union commands on N objects

Cost:

• new: N
• Union: N
• Find: 1