I have problem in implementing a disjoint set ADT in C++ due to the fact that our teacher only explained the union and find operations. I fully understand the concepts of union and find but I am still confused about how to implement them.
Could someone please give me an idea of the implementation and also explain what the interface of this data structure should look like?
You have way too many requirements, we're not here to do your homework for you.
Have a look at http://en.wikipedia.org/wiki/Disjoint-set_data_structure