title: Dealing with Union-Find algorithms with a lot of objects
body: <p>I have a problem with (not anymore with stackoverflow (hehe)) Find algorithm when trying to implement UnionFind structure algorithm with path-compression.</p>
  
  <p>I have standard array of ints, array can get pretty big -> it works fine until 60.000.000 elements.</p>
  
  <p>My Union function looks like this:</p>
  
  <pre><code>public void unite(int p, int q) {
      if(p &gt;= 0 &amp;&amp; p &lt; id.length &amp;&amp; q &gt;= 0 &amp;&amp; q &lt; id.length){
          if (isInSameSet(p, q)) return;
          id[find(p)] = find(q); 
          stevilo--;
      }
  }
  </code></pre>
  
  <p>My isInSameSet looks like this:</p>
  
  <pre><code>    public boolean isInSameSet(int p, int q) {
          if(p &gt;= 0 &amp;&amp; p &lt; id.length &amp;&amp; q &gt;= 0 &amp;&amp; q &lt; id.length) 
              return find(p) == find(q);
          return false;
  }
  </code></pre>
  
  <p>I have tried iterative way in Find:</p>
  
  <pre><code>    public int find(int i) {
          while (i != id[i]){
              id[i] = id[id[i]];
              i = id[i];              
          }       
      return i;
      }
  </code></pre>
  
  <p>and tail-recrusion:</p>
  
  <pre><code>    public int find(int i) {    
          int p = id[i];
          if (i == p) {
            return i;
          }
          return id[i] = find(p);     
       }
  </code></pre>
  
  <p>Is there anything I missed in my code? Is there any other approach to this kind of problems?</p>
  
  <p>@edit: Adding constructor to code:</p>
  
  <pre><code>    public UnionFind(int N) {
          stevilo = N;
          id = new int[N];        
          for(int i = 0; i &lt; N; i++){
              id[i] = i;
          }
  </code></pre>
  
  <p>@edit2 (better explanation and new findings):
  The problem is not in stackoverflow anymore for less then 60.000.000 elements, which is more then enough for solving my problems.</p>
  
  <p>I'm calling test Unions like this: </p>
  
  <pre><code>for(i=0;i&lt;id.length-1;i++)
  unite(i,i+1)
  </code></pre>
  
  <p>so the ending pairs are like this: </p>
  
  <pre><code>0:1, 1:2, 2:3, 3:4,.. 
  </code></pre>
  
  <p>which is only example of least optimal option for testing means only :)</p>
  
  <p>Then I check if representative of 0 is last element in table (99 for 100 elements) and it works.</p>
  
  <p>Problem is, that my algorithm works only if initial elements are each in their own union (0:0, 1:1, 2:2, 3:3). If I have different Unions already set up (0:2, 1:6, 2:1, 3:5, ...) my testing algorithm stops working. </p>
  
  <p>I have narrow it down to a problem in Find function, probably something to do with path compression </p>
  
  <pre><code>id[i] = id[id[i]].
  </code></pre>