Part C - DisjointSet Class (15 marks)

Implementation of this class is done in a1_partc.py

A DisjointSet class represents a disjoint set which is a set of sets where every element can only belong to exactly one set.

When a DisjointSet class is instantiated it is passed nothing and contains no sets. It creates an empty Python dictionary which will be used to store the elements of the DisjointSet. You are welcome to add other data members to help you implement this data structures if you wish but the restriction on other python data structures remain.

The DisjointSet has the following member functions:

def make_set(self,element)

If element already exists within the Disjoint set, the function does nothing and returns false.

If element does not exist in the DisjointSet, this function will add it to the DisjointSet by:

creating a new SetList object containing only one node, with the element as only value in the SetList

adding a new dictionary entry where element is the key and a reference to the node containing element as the value

return true

def find_set(self, element)

Function returns the representative of the set containining element.

def get_num_sets(self)

This function returns the number of sets in the DisjointSet. Note that this is not the same as the number of elements. You can start with 2 elements in unique sets and join them using the union_set() function.

def __len__(self)

This function returns the number of elements in the DisjointSet.

def get_set_size(self, element):

This function returns the size of the set containing element. If element does not exist within the disjoint set, function returns 0

def union_set(self, element1, element2)

Function performs a union of the two sets containing element1 and element2 respectively. If the two elements are already in the same set or if either of the elements do not exist, function does nothing and returns false. otherwise perform a union on the two sets, creating one set and return true