Quick Union (Lazy Approach)

Same data structure different interpretation. In this approach we are taking a tree structure in which we also store the parent of each entry.

JS implementation of Quick Union for this approach:

// Quick Union Find
class UF{
  constructor(n){
    this.id = []
    for(let i = 0; i < n; i++){
      this.id[i] = i;
    }
  }

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

  connected(p, q){
    return this.#root(p) == this.#root(q);
  }

  union(p, q){
    const i = this.#root(p);
    const j = this.#root(q);
    this.id[i] = j;
  }
}

const test = new UF(10);
console.log(test.connected(1,3))
test.union(1,3)
console.log(test.connected(1,3))

Quick Union can also be an expensive operation as our Trees can get too tall creating an expensive find operation with our root loops taking N time. The growth in operational requirement in Quick Union is Linear in nature.