Understood Quick-Find algorithm is too slow if we have many union operations. We have to design a new algorithm to do better, let’s use a lazy approach where we try to avoid doing work until we have to:
we could think the array as a set of trees where each entry contains a reference to its parent in the tree. Each element of the array has associated with it a root and we can say that two elements are connected if they have the same root.

The connected function simply checks whether given two index (p, q) their root are equal and returns.

The union function here is simpler then Quick-Find one, given two index (p, q) it retrieves their roots (i, j) and set i to j (the root of q)

The root function given an element i look for the its parent until i is equal to id[i], when we reach the root element.


package dyncon

type QuickUnionUF struct {
   Elements []int
}

func initQuickUnionUF(size int) *QuickUnionUF {
   quUF := QuickUnionUF{Elements: make([]int, size)}
   for i := range quUF.Elements {
      quUF.Elements[i] = i
   }
   return &quUF
}

func (quUF QuickUnionUF) root(i int) int {
   for i != quUF.Elements[i] {
       i = quUF.Elements[i]
   }
   return i
}

func (quUF QuickUnionUF) connected(p, q int) bool {
   return quUF.root(p) == quUF.root(q)
}

func (quUF *QuickUnionUF) union(p, q int) {
   i := quUF.root(p)
   j := quUF.root(q)
   quUF.Elements[i] = j

}

By evaluating this algorithm by the number of times it access the array we can assume the following measurements:

Algorithm initQuickUnionUF connected union
Quick-Union N tree-height tree-height

Union algorithm some times could be faster than Quick-Find but it’s too slow with tall trees!