I need to represent a family F of sets with some appropriate datastructure. The datastructure needs to support the procedures MAKE-SET(x), DISJOINT-UNION(A,B) and REPORT(A). I dont have a problem with implementing the procedures themselves. Its pretty straightforward if you follow the idea introduced in the chapter on disjoint-set data-structures in Introductions to Algorithms (CLRS for short). My problem is, in this book there is an added procedure Find(x), that, given any member of F, finds the set it belongs to by returning a representative of its set. But i am not meant to implement this procedure. So how exactly am i supposed to represent the family F? I figure we need some way of representing this collection seeing as otherwise what we have is just loose and unassociated sets. What do i do?
if it serves any interest here is the original problem statement:
We are interested in maintaining a family of sets of integers F = S1, …, Sk under the following operations:
• MAKE-SET(x ): add the set {x} til F
• REPORT(Si ): report (ex. print) all elements in Si.
• UNION(Si , Sj ): add the set Si ∪ Sj to F . delete Si og Sj from F.
• DISJOINT-UNION(S1, S2): Like UNION except it is assumed Si and Sj are disjoint, meaning., Si and Sj do no share any elements. If Si and Sj are not disjoint the result of the operation is not defined.
4.1. Come up with a datastructure, which supports MAKE-SET and DISJOINT-UNION in O(1) time and REPORT(Si ) in Θ(|Si|) time. Hint: use an appropriate list datastructure
