Implementation

• Create the DisjointSetQuiz class under the set package.

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

  Copy

  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:

  Copy

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

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:

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

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.

inSameSet(1, 3) -> true
inSameSet(1, 4) -> false

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

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

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

`inSameSet(1, 4)` -> true
`inSameSet(3, 4)` -> true

Contents

1. Concept

2. Implementation

3. Quiz

References

• Disjoint Set

Let us create the DisjointSet class:

public class DisjointSet {
    private final int[] subsets;

    public DisjointSet(int size) {
        subsets = new int[size];
        Arrays.fill(subsets, -1);
    }

    public DisjointSet(DisjointSet set) {
        subsets = Arrays.copyOf(set.subsets, set.subsets.length);
    }
}

• 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:

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

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

• 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:

public boolean inSameSet(int key1, int key2) {
    return find(key1) == find(key2);
}

• L2: returns true if the two specific keys are in the same set.

Finally, let us define the union() method:

public int union(int key1, int key2) {
    int r1 = find(key1);
    int r2 = find(key2);
    if (r1 == r2) return r1;

    if (subsets[r1] < subsets[r2]) {
        subsets[r1] += subsets[r2];
        subsets[r2] = r1;
        return r1;
    }
    else {
        subsets[r2] += subsets[r1];
        subsets[r1] = r2;
        return r2;
    }
}

• 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.