Description
Disjoint Set
In this task you have to implement the disjoint set data structure. You need to implement the following functions:
1. Make-Set (x): Makes a new set by creating a new element with a unique id, a rank of 0, and a parent pointer to itself. Time complexity: 𝑂𝑂(1).
- Find-Set (x): Finds the set that has the element x. Time complexity: 𝑂𝑂(log𝑛𝑛).
- Union (u, v): Combines two sets that contain u and v respectively, create a new set that
is a union of both sets (i.e. includes all items of both sets). Time complexity: 𝑂𝑂(log𝑛𝑛). 4. Print (u): Print the elements of set u.
******Space complexity: 𝑂𝑂(𝑛𝑛).
You should write your program using features of object-oriented programming.
Input:
Create a menu for the nine operations. Use 1-5 for the above operations sequentially and 5 for quit. Ask user to select an operation until option 5 is selected. Also prompt user for input any value which is required for the corresponding operations.
