title: Weighted Quick-Union with Path Compression algorithm
body: <p>There is a "Weighted Quick-Union with Path Compression" algorithm.</p>
  
  <p>The code:</p>
  
  <pre><code>public class WeightedQU 
  {
      private int[] id;
      private int[] iz;
  
      public WeightedQU(int N)
      {
          id = new int[N];
          iz = new int[N];
          for(int i = 0; i &lt; id.length; i++)
          {
              iz[i] = i;
              id[i] = i;
          }
      }
  
      public int root(int i)
      {
          while(i != id[i])
          {
              id[i] = id[id[i]];   // this line represents "path compression"
              i = id[i];
          }
          return i;
      }
  
      public boolean connected(int p, int q)
      {
          return root(p) == root(q);
      }
  
      public void union(int p, int q)   // here iz[] is used to "weighting"
      {
          int i = root(p);
          int j = root(q);
          if(iz[i] &lt; iz[j])
          {
              id[i] = j;
              iz[j] += iz[i];
          }
          else
          {
              id[j] = i;
              iz[i] += iz[j];
          }
      }
  }
  </code></pre>
  
  <p>Questions:</p>
  
  <ol>
  <li><p>How does the path compression work? <code>id[i] = id[id[i]]</code> means that we reach only the second ancester of our node, not the root.</p></li>
  <li><p><code>iz[]</code> contains integers from <code>0</code> to <code>N-1</code>. How does <code>iz[]</code> help us know the number of elements in the set?</p></li>
  </ol>
  
  <p>Can someone clarify this for me?</p>