# Dynamic Connectivity: Quick-Union in Go

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!