Union Find in Java

Question

I am trying to implement the union-find algorithm. Basically the part of the algorithm that I am struggling with is the union part. What is supposed to happen is that there is a list of numbers (starts off with all of them being their index in the list) and if two numbers happen to have the same value then it means that they are connected. When the union happens like say Union(1,6) then the list would go from [0,1,2,3,4,5,6,7,8] to [0,6,2,3,4,5,6,7,8] (assuming the array was size 9 to start). My way of implementing this is shown here:

public class QuickFindUF {
    private int[] id;
    
    public QuickFindUF(int N) {
        id = new int[N];
        for (int i=0; i < N; i++) {
            id[i] = i;
        }       
    }
    
    public boolean connected(int p, int q) {
        return id[p]==id[q];
    }
    
    public void Union(int p, int q) {
        for (int i=0; i < id.length; i++) {
            if (id[i] == id[p]) {
                id[i] = id[q];
            }
        }
    }
    public void printID() {
        for (int i = 0; i < id.length; i++) {
            System.out.print(id[i]);
        }
    }
    
    
    public static void main(String[] args) {
        QuickFindUF quickfind = new QuickFindUF(9);
        quickfind.printID();
        System.out.println();
        quickfind.Union(1,6);
        quickfind.printID();
        
        
    }
}

However, the professor while going over this said that this was not right and that the union function should instead look like this:

public void Union(int p, int q) {
        int pid = id[p];
        int qid = id[q];
        for (int i=0; i < id.length; i++) {
            if (id[i] == pid) {
                id[i] = qid;
            }
        }
    }

Both versions work and will change id so that it is [0,6,2,3,4,5,6,7,8] like it should be which makes me think that there's something under the hood that makes the way I did it wrong but I don't even know where to begin on what that could be. I'm fairly new to Java so I'm guessing it I just haven't been exposed to it before. Any help would be greatly appreciated.

Answer 1

Your algorithm is logically incorrect, because it changes the value of id[p] in the middle of the loop, and therefore fails to update occurrences which occur after index p. Consider this example:

int[] id = { 1, 1, 1, 4, 4 };
int p = 0, q = 3;

for(int i = 0; i < id.length; i++) {
    if(id[i] == id[p]) {
        id[i] = id[q];
    }
}

System.out.println(Arrays.toString(id));

Output:

[4, 1, 1, 4, 4]

The correct output would be:

[4, 4, 4, 4, 4]