mp_mazes
Maddening 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) 
This function should return the number of nodes in the uptree containing the element. 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.
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  ) 
This function should return the number of nodes in the uptree containing the element.