import java.util.*;
public class UnionFind<V>{

	public static class Node<V>{
		public V value;
		public Node(V v){
			value= v;
		}
	}

	private HashMap<Node<V>,Node<V>> parents;
	private HashMap<V,Node<V>> nodes;
	private HashMap<Node<V>,Integer> sizeMap;

	public UnionFind(List<V> arr){
		parents = new HashMap<Node<V>,Node<V>>();
		nodes = new HashMap<V,Node<V>>();
		sizeMap = new HashMap<Node<V>,Integer>();
		for (V cur : arr ) {
			Node<V> n = new Node<V>(cur);
			nodes.put(cur,n);
			parents.put(n,n);
			sizeMap.put(n,1);
		}
	}

	private Node<V> Find(V node){
		Stack<Node<V>> stack = new Stack<Node<V>>();
		Node<V> cur = nodes.get(node);
		while(cur != parents.get(cur)){
			stack.push(cur);
			cur = parents.get(cur);
		}

		while(!stack.isEmpty()){
			parents.put(stack.pop(),cur);
		}
		return cur;
	}

	public void Union(V a,V b){
		Node<V> fa = Find(a);
		Node<V> fb = Find(b);

		if(fa != fb){
			int sa = sizeMap.get(fa);
			int sb = sizeMap.get(fb);

			Node<V> big = sa>=sb ? fa : fb;
			Node<V> small = big==fa ? fb : fa;

			parents.put(small,big);
			sizeMap.remove(small);
		}
	}

	public int size(){
		return sizeMap.size();
	}









	public static void main(String[] args){
		ArrayList<Integer> arr = new ArrayList<Integer>();
		arr.add(1);
		arr.add(11);
		arr.add(111);
		arr.add(1111);
		arr.add(21);
		arr.add(31);
		arr.add(41);
		UnionFind<Integer> unionFind = new UnionFind<Integer>(arr);
		System.out.println("size ="+ unionFind.size());
		unionFind.Union(1,11);
		System.out.println("size ="+ unionFind.size());
		unionFind.Union(1111,11);
		System.out.println("size ="+ unionFind.size());
		unionFind.Union(1,1111);
		System.out.println("size ="+ unionFind.size());


	}
}