6.3. Quiz

This section provides exercises for better understanding in disjoint sets.

Implementation

• Create the DisjointSetQuiz class under the set package.

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

  public int find(int id) {
      return (subsets[id] < 0) ? id : find(subsets[id]);
  }

• A disjoint set can be represented by a tree. Update the main() 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 subsets[] array changes after each call in the main() method.
• Describe how the values in the subsets[] 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:

  public int find(int id) {
      return (subsets[id] < 0) ? id : (subsets[id] = find(subsets[id]));
  }