Disjoint Set

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