I have implemented the disjoint set data structure using Java. It supports:

• add: Adding an element x
• find: Finding the parent of an element x (with path compression)
• merge: Merge two sets x and y
• split: Change the parents of all elements in c from oldParent to newParent
• getSetCount: Get the number of sets

public class DisjointSet {
    private final HashMap<Integer, Integer> parent;
    private int setCount;

    public DisjointSet() {
        this.parent = new HashMap<>();
        this.setCount = 0;
    }

    public int getSetCount() {
        return setCount;
    }

    public void add(int x) {
        parent.put(x, x);
        setCount++;
    }

    public int find(int x) {
        int parentX = parent.get(x);
        if (parentX == x) {
            return x;
        }
        parentX = find(parentX);
        parent.put(x, parentX);
        return parentX;
    }

    public boolean merge(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);
        if (parentX != parentY) {
            parent.put(parentX, parentY);
            setCount--;
            return true;
        }
        return false;
    }

    public void split(Collection<Integer> c, int oldParent, int newParent) {
        for (Integer x : c) {
            parent.put(x, newParent);
        }
        setCount++;
    }
}

The problem is, after merging and splitting multiple times, the disjoint set becomes buggy: I find that two elements are not in the same set (i.e. have different parents), while they are supposed to be. I try to updated the parents of all elements in c before splitting, but it doesn’t work:

    public void split(Collection<Integer> c, int oldParent, int newParent) {
        // This doesn't fix the bug.
        for (Integer x : c) {
            find(x);
        }
        for (Integer x : c) {
            parent.put(x, newParent);
        }
        setCount++;
    }

However, if I update the parents of all elements before the split operation, the bug got fixed:

    public void split(Collection<Integer> c, int oldParent, int newParent) {
        // This fixes the bug.
        for (Integer x : parent.keySet()) {
            find(x);
        }
        for (Integer x : c) {
            parent.put(x, newParent);
        }
        setCount++;
    }

I don’t understand why I need to update the parents of all elements, even if they don’t need to be split.

What is the correct way of performing the split operation on a disjoint set? Or do I have to rebuild the disjoint set because it doesn’t support splitting at all?