Quick Union

This approach is similar to Quick Find in that each vertex (object) is given an ID. However, the ID is used to link one node to another to form "parent/child" relationship as in a tree structure.

• connected(p,q): check if $p$ and $q$ have the same root (i.e., following their parents we reach the same root object).
• union(p,q): to merge components containing $p$ and $q$, set the root of the component containing $q$ to be direct child of the root of the component containing $p$.

Exercise What is the complexity of core operations under "Quick Union" implementation?

// chase parent pointers until reach root
private int root(int x) { 
  while (x != id[x]) {
    x = id[x]; 
  }
  return x; 
}