#include <iostream>
#include <set>
#include "DisjSets.h"

using namespace std;



void DisjSets::unionSets( int root1, int root2 )
{
	if ( s[root2] < s[root1] ) //// root2 is deeper
	{
		//make root2 new root
		s[root1] = root2;
	}
	else////root1
	{
		if ( s[root1] == s[root2] )
			s[root1]--;		//Update height if same else the height is the larger root's height
		s[root2] = root1;
	}
}

int DisjSets::Find( int x )
{
	if (s[x] < 0)
	{
		return x;
	}else
	{
		//Find the parent recursivly and on way back set to root
		return s[x] = Find( s[x] );
	}

}

void DisjSets::Union( int x, int y )
{
	unionSets( Find(x), Find (y) );
}


DisjSets::DisjSets( int numElements ) : s(numElements)
{
	for (unsigned int i = 0; i < s.size(); i++)
		s[i] = -1;
}