import java.util.ArrayList;


/**
  * A class to implement the Disjoint Sets Data Structure
  */
public class DisjointSets {

	private ArrayList<Integer> theSets;

	/**
	  *@param numberOfSets is the number of disjoints sets
	  */
	public DisjointSets(int numberOfSets) {
		theSets = new ArrayList<Integer>(numberOfSets);
		for( int i = 0; i < numberOfSets; i++ ) theSets.add(-1);
	}// end constructor

	/**
	  * Performs the set union
	  *@param A is a set
	  *@param B is another set
	  */
	public void union(int a, int b) { // uses union by size
		if( theSets.get(a) < theSets.get(b) ) {
			theSets.set(a,theSets.get(a) + theSets.get(b));
			theSets.set(b,a);
		} else {
			theSets.set(b,theSets.get(a) + theSets.get(b));
			theSets.set(a,b);
		}
	}

	private int parent(int n) {
		return theSets.get(n);
	}

	/**
	  * Returns the set containing a particular element
	  *@param n is the element
	  *@return the name of the set containing n
	  */
	public int get(int n) { // uses path compression
		int name;
		if( parent(n) < 0 ) {
			name = n;
		} else {
			name = get(parent(n));
			theSets.set(n,name);
		}
		return name;
	}

	public String toString() {
		String out = "";
		for( int x : theSets) {
			out = out + x + " ";
		}
		return out;
	}


}