java - Union By Size Infinite Loop -

i working on implementing union-find data structure scratch , encountering problem infinite loop results in find method if attempting repeat union call.

i implementing union size, find using path compression. have created test implementation of 10 elements (0 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 doing second u 0 2, loop gets caught because value @ index 2 zero, , root zero, repeating loop cyclically. same logic follows when attempt u 1 4. 2nd loop in find has incorrect logic.

my question is: how can handle theses cases don't caught in infinite loop?

this find method:

/*  * search element 'num' , returns key in root of tree  * containing 'num'. implements path compression on each find.   */ public int find (int num) {     totalpathlength++;     int k = num;     int root = 0;     // find root     while (sets[k] >= 0) {         k = sets[k];         totalpathlength++;     }     root = k;     k = num;      // point nodes along path root     /* infinite loop occurs here */     while (sets[k] >= 0) {         sets[k] = root;     }     return root; } 

how calling find in relation union: (located in main)

   int x = integer.parseint(tokens[1]);    int y = integer.parseint(tokens[2]);    // call find upon 2nd: u 0 2, results in inf. loop    if (uf.find(x) == x && uf.find(y) == y) {         uf.union(x, y);    } 

you not traverse path in second loop. means either num root or method enters infinite loop. change loop this:

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