Union-find: connectivity without repeated graph searches

type DisjointSet struct {
	parent, size []int
	Components   int
}

// Caller supplies a nonnegative n and valid IDs to Find and Union.
func NewDisjointSet(n int) *DisjointSet {
	d := &DisjointSet{parent: make([]int, n), size: make([]int, n), Components: n}
	for i := range d.parent {
		d.parent[i] = i
		d.size[i] = 1
	}
	return d
}
func (d *DisjointSet) Find(x int) int {
	for x != d.parent[x] {
		d.parent[x] = d.parent[d.parent[x]]
		x = d.parent[x]
	}
	return x
}
func (d *DisjointSet) Union(a, b int) bool {
	a, b = d.Find(a), d.Find(b)
	if a == b {
		return false
	}
	if d.size[a] < d.size[b] {
		a, b = b, a
	}
	d.parent[b] = a
	d.size[a] += d.size[b]
	d.Components--
	return true
}