MP7
Mazes

Each DisjointSets object represents a family of disjoint sets, where each element has an integer index. More...
#include "dsets.h"
Public Member Functions  
void  addelements (int num) 
Creates n unconnected root nodes at the end of the vector. More...  
int  find (int elem) 
This function should compress paths and works as described in lecture. More...  
void  setunion (int a, int b) 
This function should be implemented as unionbysize. More...  
int  size (int elem) 
Return the size of the uptree containing elem. More...  
Each DisjointSets object represents a family of disjoint sets, where each element has an integer index.
It is implemented with the optimizations discussed in class, as uptrees stored in a single vector of ints. Specifically, path compression and unionbysize are used. Each place in the vector represents a node. (Note that this means that the elements in our universe are indexed starting at 0.) A nonnegative number is the index of the parent of the current node; a negative number in a root node is the negative of the set size.
Note that the default compilersupplied Big Three will work flawlessly because the only member data is a vector of integers and this vector should initially be empty.
void DisjointSets::addelements  (  int  num  ) 
Creates n unconnected root nodes at the end of the vector.
num  The number of nodes to create 
int DisjointSets::find  (  int  elem  ) 
This function should compress paths and works as described in lecture.
elem  The element whose root is to be found 
void DisjointSets::setunion  (  int  a, 
int  b  
) 
This function should be implemented as unionbysize.
That is, when you setunion two disjoint sets, the smaller (in terms of number of nodes) should point at the larger. This function works as described in lecture, except that you should not assume that the arguments to setunion are roots of existing uptrees.
Your setunion function SHOULD find the roots of its arguments before combining the trees. If the two sets are the same size, make the tree containing the second argument point to the tree containing the first. (Note that normally we could break this tie arbitrarily, but in this case we want to control things for grading.)
a  Index of the first element to union 
b  Index of the second element to union 
int DisjointSets::size  (  int  elem  ) 
Return the size of the uptree containing elem.
elem  The elem whose uptree's size is returned 