Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
A partition is a set of sets. Consequently, there are two related issues to consider when developing an approach for representing partitions:
For example, Figure 
shows how the partition
can be represented using a forest.
Notice that each element of the universal set 
appears in exactly one node of exactly one tree.
Figure: Representing a Partition as a Forest
The trees in Figure have some very interesting characteristics.
The first characteristic concerns the shapes of the trees:
The nodes of the trees have arbitrary degrees.
The second characteristic concerns the positions of the keys:
there are no constraints on the positions of the keys in a tree.
The final characteristic has to do with the way the tree is represented:
Instead of pointers to its children,
each node of a tree contains only one pointer--a pointer to its parent!
Since there is no particular order to the nodes in the trees,
it is necessary to keep track of the position of each node explicitly.
Figure shows how this can be done using an array of pointers.
(This figure shows the same partition as in Figure ).
The array contains a pointer for each element of the universal set U.
Specifically, the 
array element contains a pointer
to the node that contains item i.
Having found the desired node,
we can follow the chain of parent pointers
to find the root of the corresponding tree.
Figure: Finding the Elements of a Partition
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.