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}