import java.util.*;
import java.io.*;

public class DisjointSetTest {
	
	// The size for testing the DisjointSet
	private static int SIZE = 10;
	
	public static void main(String[] Args){
		
		// Initialize the Disjoint Set
		DisjointSet ds = new DisjointSet(SIZE);
	
		// Merge sets randomly
		for (int i = 0; i < SIZE * 3; i++){
			
			// Select a first and second element to union/merge
			int a = (int) (Math.random() * SIZE);
			int b = (int) (Math.random() * SIZE);
			
			// Union the two selected elements
			if (ds.union(a, b)) {
				
				// Tell the user the sets were unioned/merged successfully
				System.out.println("Successfully merged " + a + " " + b);
			} else {
				
				// Inform the user that the elements could not be merged
				System.out.println("Elements were already in the same set (" + 
					a + ", " + b + ")");
			}
			
			// Print out the parents of the elements
			for (int j = 0; j < SIZE; j++){
				System.out.print(ds.parent[j] + " ");
			}
			
			// Add a new line 
			System.out.println();
		}
	}
	
	public static class DisjointSet {
		int[] parent;
		int[] height;
		
		DisjointSet(int n) {
			
			// Initialize the parents such that each element is their own root
			parent = new int[n];
			for (int i = 0; i < n; i++){
				parent[i] = i;
			}
			
			// Initialize the heights of all trees as zero
			height = new int[n];
		}
		
		int find(int element){
			
			// Check if th node has no parents
			if (parent[element] == element){
				// Returns the root of the tree if we are at the root
				return element;
			}
			
			// Look for the root of the tree recursively since the current
			// element is not the root
			int findParent = find(parent[element]);
			
			// Do path compression (optional)
			// parent[element] = findParent;
			
			// Return the root of the tree
			return findParent;
		}
		
		boolean union(int first, int second) {
			int repFirst = find(first);
			int repSecond = find(second);
			
			// Check if the elements belong to the same tree
			if (repFirst == repSecond) {
				return false;
			}
			
			// Check if the first tree is taller than the second tree
			if (height[repFirst] > height[repSecond]){
				
				// Make the second tree's root have a parent
				// (the root of the first tree)
				parent[repSecond] = repFirst;
			} 
			// Check if the second tree is taller than the first
			else if (height[repFirst] < height[repSecond]){
				
				// Make the first tree's root have a parent 
				// (the root of the second tree)
				parent[repFirst] = repSecond;
			} 
			// The trees have equal height
			else {
				// Their equal need to bookkeep on the height
				parent[repFirst] = repSecond;
				
				// Update the height of the larger tree
				height[repSecond]++;
			}
			
			// Tell that the trees were indeed merged
			return true;
		}
	}
}