union

public class UnionFindStructure<E> {
  private class Locator<E> implements Position<E> {
      public E element;
      public int size;
      public Locator<E> parent;

      public Locator(E elem) {
          element = elem;
          size = 1;
          parent = this;
      }
      public E getElement() { return element; }
  }

  public Position<E> makeCluster(E e) { return new Locator<>(e); }
  public Position<E> find(Position<E> p) {
      Locator<E> loc = validate(p);
      if (loc.parent != loc)
          loc.parent = (Locator<E>) find(loc.parent);
      return loc.parent;
  }
  public void union(Position<E> p, Position<E> q) {
      Locator<E> a = validate(p);
      Locator<E> b = validate(q);
      if (a != b) {
          if (a.size > b.size) {
              b.parent = a;
              a.size += b.size;
          } else {
              a.parent = b;
              b.size += a.size;
          }
      }
  }

  private Locator<E> validate(Position<E> p) throws IllegalArgumentException {
      if (!(p instanceof Locator)) throw new IllegalArgumentException();
      Locator<E> l = (Locator<E>) p;
      return l;
  }
}