A disjoint set enables to be join sets efficiently. There are two methods implemented in this structure, inSameSet() and union().

In the following example, each key in {0, 1, 2, 3, 4} is initially in its own set:

0: {0}
1: {1}
2: {2}
3: {3}
4: {4}

inSameSet(1, 3) checks if the keys 1 and 3 are in the same set:

inSameSet(1, 3) -> false

The union(1, 3) method joins two sets including 1 and 3 as one set:

If we check if the keys 1 and 3 are in the same set, it should return true although for the keys 1 and 4, it should return false.

The union(3, 4) method joins the two sets including 3 and 4 as one:

If we check if 1, 3 and 4 are in the same set, it should return true:

Contents

1. Concept

References

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.

Implementation

• Create the DisjointSetQuiz class under the set package.

• Assume that the method in the DisjointSet class uses the baseline approach:

• A disjoint set can be represented by a tree. Update the method in the DisjointSetQuiz class that would result the following tree:

Report

Write a report quiz6.pdf that includes the followings:

• Describe how the values in the array changes after each call in the main() method.

• Describe how the values in the array would change after calling find(0) once all keys are added as above, assuming that the find() method in DisjointSet class uses the efficient approach: