UFDS.java

public class UFDS {

	private int numSets, p[], rank[], setSize[];
	
	public UFDS(int n) {
		this.numSets = n;
		this.p = new int[n];
		this.rank = new int[n];
		this.setSize = new int[n];
		for(int i = 0;i < n;++i){ p[i] = i; rank[i] = 0; setSize[i] = 1; }
	}
	public int findSet(int i){
		if(p[i] == i) return i;
		p[i] = findSet(p[i]);
		return p[i];
	}
	public boolean isSameSet(int i, int j) {return findSet(i) == findSet(j);}
	public void unionSet(int i, int j){
		if(isSameSet(i, j))
			return;
		numSets--;
		int x = findSet(i), y = findSet(j);
		if(rank[x] > rank[y]) {p[y] = x; setSize[x] += setSize[y];}
		else {
			p[x] = y; setSize[y] += setSize[x];
			if(rank[x] == rank[y]) rank[y]++;
		}
	}
	public int numDisjointSets() { return numSets; }
	public int sizeOfSet(int i) { return setSize[findSet(i)]; }
}