6.2. Implementation

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);
    }
}

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

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;
    }
}