| A disjoint set is a generic data structure that represents a collection of
sets that are assumed to be disjoint (no object exists in more than
one set).
This disjoint set implementation represents the disjoint set as a forest,
where the nodes of each tree all belong to the same set. This implementation
uses path compression in the findSet implementation to flatten each tree
to a constant depth. A rank is maintained for each tree that is used when
performing union operations to ensure the tree remains balanced.
Ref: Cormen, Leiserson, and Rivest Introduction to Algorithms,
McGraw-Hill, 1990. The disjoint set forest implementation in section 22.3.
since:
3.2 |
