Union find with path compression and weighted union

UnionFind.java

package hruntek;

/**
 * Union find with path compression and weighted union
 * O(log*N) operations
 */
class UnionFind {

	/**
	 * Node's id
	 */
	private final int[] id;

	/**
	 * Size of tree below that node
	 */
	private final int[] size;

	/**
	 * Creates a new union find structure with given number of nodes
	 *
	 * @param n number of nodes
	 */
	UnionFind(int n) {
		id = new int[n];
		size = new int[n];
		for (int i = 0; i < n; i++) {
			id[i] = i;
			size[i] = 1;
		}
	}

	/**
	 * @param x first node
	 * @param y second node
	 * @return true if they are connected
	 */
	boolean areConnected(int x, int y) {
		return find(x) == find(y);
	}

	/**
	 * Connects two nodes
	 *
	 * @param x first node
	 * @param y second node
	 */
	void union(int x, int y) {
		int rootX = find(x);
		int rootY = find(y);

		if (rootX == rootY) {
			return;
		}

		// smaller root points to larger one
		if (size[rootX] < size[rootY]) {
			id[rootX] = rootY;
			size[rootY] += size[rootX];
		} else {
			id[rootY] = rootX;
			size[rootX] += size[rootY];
		}
	}

	/**
	 * Find root node of given node
	 *
	 * @param x node
	 * @return root node
	 */
	private int find(int x) {
		int n = id.length;
		if (x < 0 || x >= n) {
			throw new IndexOutOfBoundsException("index " + x + " not between 0 and " + (n - 1));
		}

		return find_(x);
	}
	
	/**
	 * path compression: makes tree almost flat
	 */
	private int find_(int x){
		if (x != id[x]) id[x] = find_(id[x]);
		return id[x];
	}

}