#include <iostream.h>
#include <stdlib.h>
#include "UnionFind.h"

UnionFind::UnionFind(int num_sets)
{
  _numSets = num_sets;
  _setID = new int[_numSets];

  reset();
}

UnionFind::~UnionFind()
{
  delete [] _setID;
}


void
UnionFind::reset(void)
{
  int i;

  for (i = 0; i < _numSets; i++) {
    _setID[i] = -1;
  }
}


int
UnionFind::numElements(void)
{
  return _numSets;
}


int
UnionFind::find(int id)
{
  if (_setID[id] >= 0) 
    _setID[id] = find(_setID[id]);
  else
    return id;

  return _setID[id];
}


void
UnionFind::setUnion(int idx1, int idx2)
{
  int sid1 = find(idx1);
  int sid2 = find(idx2);

  if (_setID[sid1] > _setID[sid2]) {
    _setID[sid2] += _setID[sid1];
    _setID[sid1] = sid2;
  } else {
    _setID[sid1] += _setID[sid2];
    _setID[sid2] = sid1;
  }
}