This sections discusses the implementation of disjoint sets.
Let us create the DisjointSet
class:
L2
: the size of subset (-1
implies 1
ID, -2
implies 2
IDs, and so on).
L5-6
: every set is initialized with the size of 1
.
L9
: a copy constructor.
Let us define the find()
method:
L2
: returns the ID of the subset where the specific key belongs to.
What is the worst-case complexity of the
find()
method?
We then define the inSameSet()
method:
L2
: returns true if the two specific keys are in the same set.
Finally, let us define the union()
method:
L2-4
: return the subset ID where both key1
and key2
belongs to.
L6-10
: merges the set containing key2
to the set containing key1
.
L11-15
: merges the set containing key1
to the set containing key2
.