Method Find

graph/unionfind.go:37–42

Find finds the root of the set to which the given element belongs. It performs path compression to make future Find operations faster.

(q int)

// Find finds the root of the set to which the given element belongs.
// It performs path compression to make future Find operations faster.
func (u *UnionFind) Find(q int) int {
	if q != u.parent[q] {
		u.parent[q] = u.Find(u.parent[q])
	}
	return u.parent[q]
}

// Union merges the sets, if not already merged, to which the given elements belong.
// It performs union by rank to keep the tree as flat as possible.