package dokumenty;

/**
 * Classic Union-Find algorithm.
 * To be found in any good computer science book.
 * 
 * @author Mariusz Paradowski
 */
public class UnionFind {
	private int[] parrent;
	
	/**
	 * Constructor. We have to declare the available number of groups.
	 * It executes the "MakeSet" operation for every group.
	 */
	public UnionFind(int groups) {
		this.parrent = new int[groups];
		for (int i = 0; i < parrent.length; i++) {
			this.parrent[i] = i;
		}
	}
	
	/**
	 * Makes an union of two sets.
	 */
	public void union(int i, int j) {
		int iPar = this.find(i);
		int jPar = this.find(j);
		
		if (iPar != jPar) {
			if (iPar < jPar) {
				this.parrent[jPar] = iPar;
			} else {
				this.parrent[iPar] = jPar;
			}
		}
	}
	
	/**
	 * Returns the number of set for the given element.
	 */
	public int find(int i) {
		if (this.parrent[i] == i) {
			return i;
		}
		this.parrent[i] = this.find(this.parrent[i]);
		return this.parrent[i];
	}
	
	/**
	 * An additional operator. Returns the set size for the given element.
	 */
	public int setSize(int i) {
		int set = this.find(i);
		int counter = 0;
		for (int j = 0; j < this.parrent.length; j++) {
			if (set == this.find(j)) {
				counter++;
			}
		}
		return counter;
	}
}