Disjoint Sets

An implementation of disjoint sets on the integers 0, ..., n - 1.

The operator << has been overloaded to print the disjoint set data structure as is shown here:

Size:           16
Height:         0
Number of Sets: 16
Parent:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Entry:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Sets: {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}, {12}, {13}, {14}, {15}

The disjoint sets are printed at the bottom.

After sixteen random unions, the output is:

Size:           16
Height:         2
Number of Sets: 8
                            |                           
                   |        |                 |        |
Parent:   0 15 12  6  4  5  6  6  8  3 12 12 12  3 14 15
Entry:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Sets: {0}, {4}, {5}, {3,6*,7,9,13}, {8}, {2,10,11,12*}, {14}, {1,15*}

The bars are a visual indication of the height of the tree rooted at that entry; one may note the path of 9→3→6 which results in a tree of height 2. For any of the disjoint sets printed in the last line, if it has more than two entries, the root of the tree is starred.

After a sufficient number of unions to result in a single set with the output:

Size:           16
Height:         3
Number of Sets: 1
                                  |                     
                            |     |                     
                   |        |     |           |        |
Parent:   8 15 12  6  8  8  8  6  8  3 12 12  8  3  8  8
Entry:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Sets: {0,1,2,3,4,5,6,7,8*,9,10,11,12,13,14,15}