6.2. Implementation

This sections discusses the implementation of disjoint sets.

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:

Baseline

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

Efficient

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.