Disjoint Set Data Structure

DisjointSet.java

public class DisjSets
{
  public DisjSets( int numElements )
  {
    s = new int [ numElements ];
    
    for ( int i = 0; i < s.length; ++i )
      s[i] = -1;
  }
  
  /**
   * union by ranks.
   * 
   * @param root1 - the root of set 1.
   * @param root2 - the root of set 2.
   */
  public void union( int root1, int root2 )
  {
    if ( s[root2] < s[root1] )
      s[root1] = root2; // root2 is deeper, make root2 new root
    else
    {
      if ( s[root1] == s[root2] )
        s[root1]--; // update ranks if the same
      s[root2] = root1; // make root1 new root
    }
  }
  
  /**
   * find with path compression.
   * 
   * @param x - the element being searched for.
   * @return - the set containing x.
   */
  public int find( int x )
  {
    if ( s[x] < 0 )
      return x;
    else
      return s[x] = find( s[x] );
  }
  
  private int [] s;
}