A disjoint-set data structure maintains a collection $$\mathcal{S} = \{S_{1}, S_{2}, \dots, S_{k}\}$$ of disjoint dynamic sets.

## A weighted-union heuristic

### Theorem 1

Using linked-list representation of disjoint sets and the weighted union heuristic, a sequence of $$m$$ MAKE-SET, UNION, and FIND-SET operations, $$n$$ of which are MAKE-SET operations, takes, $$O(m + n \lg{n})$$ time.

## References

1. Introduction to Algorithms, MIT Press