Path Compression

We can further optimise the Weighted Quick Union by adding compression to the algorithm. The concept is simple, as we loop through each node we update the root of those nodes further compressing our connected component tree structure reducing computing requirements in future FIND operations.

To modify the operation we add one line of code!

  #root(i) {
    while (i != this.id[i]) {
      this.id[i] = this.id[this.id[i]];
      i = this.id[i];
    }
    return i;
  }

Side Note: See Here for how applications spark some amazing math propositions.

Extra reading material: Iterated Logarithm Ackermann Function