Quick Union

This approach is similar to Quick Find in that each vertex (object) is given an ID. However, the ID links one node to another to form a "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 a 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; 
}