BUGFIX-66

Bug 23: Union-Find Lost And Found

This is the most efficient known disjoint-set algorithm: Martin Rem's union-find.
The representative of a set (as returned by the Find method) is the set's lowest-numbered node.
The Union method uses a sorted-merge traversal, moving along the path to the higher-numbered parent.
The link to the higher-numbered parent is replaced by a link to the lower-numbered parent.
Union returns true if two sets were joined. It returns false if both nodes were already in the same set.
The Find method uses path-halving: To flatten the tree, every other node is linked to its grandparent.

Fix The Tiny Bug In This Go Code:

type Rem struct { arc []int } func NewRem(n int) *Rem { a := make([]int, n) for i := range a { a[i] = i } return &Rem{ arc: a, } } func (r *Rem) Union(i1, i2 int) bool { var ( arc1 = r.arc[i1] arc2 = r.arc[i2] ) for { switch { case arc1 == arc2: return false case arc1 < arc2: r.arc[i2] = arc1 if i2 == arc2 { return true } i2 = arc2 arc2 = r.arc[i2] default: r.arc[i1] = arc2 if i1 == arc1 { return true } i1 = arc1 arc1 = r.arc[i1] } } } func (r *Rem) Find(i1 int) int { for { i2 := r.arc[i1] if i2 == i1 { return i1 } i3 := r.arc[i2] if i3 == i2 { return i1 } r.arc[i1] = i3 i1 = i3 } }

To receive a hint, submit unfixed code.