Union By Size Infinite Loop

Question

I am working on implementing a Union-Find data structure from scratch and am encountering a problem where an infinite loop results in my find method if attempting to repeat a union call.

I am implementing Union By Size, with find using path compression. I have created a test implementation of only 10 elements (0 to N-1)

Example:

U 3 1  //Union 1 -> 3
U 0 2  //Union 2 -> 0
U 0 2  //Union 2 -> 0 , infinite loop results
U 1 4  //Union 4 -> 1 , results in infinite loop

When I am doing the second U 0 2, the loop gets caught because the value at index 2 is zero, and the root is also zero, thus repeating the loop cyclically. The same logic follows when I attempt to do U 1 4. My 2nd loop in find has incorrect logic.

My question is: How can I handle theses cases so that I don't get caught in this infinite loop?

This is my find method:

/*
 * Search for element 'num' and returns the key in the root of tree
 * containing 'num'. Implements path compression on each find. 
 */
public int find (int num) {
    totalPathLength++;
    int k = num;
    int root = 0;
    // Find the root
    while (sets[k] >= 0) {
        k = sets[k];
        totalPathLength++;
    }
    root = k;
    k = num;

    // Point all nodes along path to root
    /* INFINITE LOOP OCCURS HERE */
    while (sets[k] >= 0) {
        sets[k] = root;
    }
    return root;
}

How I am calling find in relation to union: (located in main)

   int x = Integer.parseInt(tokens[1]);
   int y = Integer.parseInt(tokens[2]);
   // Call to find upon the 2nd: U 0 2, results in inf. loop
   if (uf.find(x) == x && uf.find(y) == y) {
        uf.union(x, y);
   }

Answer 1

You do not traverse the path in the second loop. That means you either num is a root or your method enters a infinite loop. Change your loop like this:

while (sets[k] >= 0) {
    // save old parent to variable
    int next = sets[k];

    sets[k] = root;
    k = next;
}