UVa 10158 - War

// UVa 10158 - War

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	private static final int NOBODY = -1;

	private static UnionSet<Integer> unionSet;

	private static int[] enemyOf;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();

		unionSet = new UnionSet<Integer>();
		enemyOf = new int[n];
		for (int i = 0; i < n; i++) {
			unionSet.makeSet(i);
			enemyOf[i] = NOBODY;
		}

		int codeOfTheOperation = scanner.nextInt();
		int x = scanner.nextInt();
		int y = scanner.nextInt();
		while (codeOfTheOperation != 0) {
			switch (codeOfTheOperation) {
			case 1:
				if (areEnemies(x, y))
					System.out.println(-1);
				else
					setFriends(x, y);
				break;
			case 2:
				if (areFriends(x, y))
					System.out.println(-1);
				else
					setEnemies(x, y);
				break;
			case 3:
				System.out.println(areFriends(x, y) ? 1 : 0);
				break;
			case 4:
				System.out.println(areEnemies(x, y) ? 1 : 0);
				break;
			}
			codeOfTheOperation = scanner.nextInt();
			x = scanner.nextInt();
			y = scanner.nextInt();
		}
	}

	private static void setFriends(int x, int y) {
		Integer rootX = unionSet.getRoot(x);
		Integer rootY = unionSet.getRoot(y);
		Integer enemyX = enemyOf[rootX];
		Integer enemyY = enemyOf[rootY];
		unionSet.union(x, y);

		Integer newRoot = unionSet.getRoot(rootX);
		if (enemyX != enemyY && enemyX != NOBODY && enemyY != NOBODY) {
			unionSet.union(enemyX, enemyY);
			Integer newEnemy = unionSet.getRoot(enemyX);
			enemyOf[newRoot] = newEnemy;
		} else if (enemyX != NOBODY) {
			enemyOf[newRoot] = enemyX;
		} else if (enemyY != NOBODY) {
			enemyOf[newRoot] = enemyY;
		}
	}

	private static void setEnemies(int x, int y) {
		Integer rootX = unionSet.getRoot(x);
		Integer rootY = unionSet.getRoot(y);

		Integer enemyX = enemyOf[rootX];
		Integer enemyY = enemyOf[rootY];

		if (enemyX == NOBODY) {
			enemyOf[rootX] = rootY;
		}
		if (enemyY == NOBODY) {
			enemyOf[rootY] = rootX;
		}
		if (enemyOf[rootX] == rootY && enemyOf[rootY] == rootX)
			return;

		if (enemyOf[rootX] != rootY)
			unionSet.union(enemyOf[rootX], rootY);
		if (enemyOf[rootY] != rootX)
			unionSet.union(enemyOf[rootY], rootX);
	}

	private static boolean areFriends(int x, int y) {
		return unionSet.areOnSameSet(x, y);
	}

	private static boolean areEnemies(int x, int y) {
		Integer rootX = unionSet.getRoot(x);
		Integer rootY = unionSet.getRoot(y);
		return enemyOf[rootX] == rootY;
	}

	private static class UnionSet<T> {

		private Map<T, UnionSetElement<T>> dataToElement = new HashMap<T, UnionSetElement<T>>();

		public void makeSet(T data) {
			dataToElement.put(data, createElement(data));
		}

		public void makeSets(Iterable<T> datas) {
			for (T data : datas) {
				dataToElement.put(data, createElement(data));
			}
		}

		public boolean areOnSameSet(T x, T y) {
			UnionSetElement<T> xElement = dataToElement.get(x);
			UnionSetElement<T> yElement = dataToElement.get(y);
			return find(xElement) == find(yElement);
		}

		public T getRoot(T x) {
			UnionSetElement<T> element = dataToElement.get(x);
			UnionSetElement<T> root = find(element);
			return root.data;
		}

		public void union(T a, T b) {
			UnionSetElement<T> aElement = dataToElement.get(a);
			UnionSetElement<T> bElement = dataToElement.get(b);
			union(aElement, bElement);
		}

		private UnionSetElement<T> createElement(T data) {
			UnionSetElement<T> element = new UnionSetElement<T>();
			element.parent = element;
			element.rank = 0;
			element.data = data;
			return element;
		}

		// i.e. getRoot
		private UnionSetElement<T> find(UnionSetElement<T> element) {
			if (element.parent != element) {
				element.parent = find(element.parent);
			}
			return element.parent;
		}

		private void union(UnionSetElement<T> x, UnionSetElement<T> y) {
			UnionSetElement<T> xRoot = find(x);
			UnionSetElement<T> yRoot = find(y);
			if (xRoot == yRoot)
				return;

			// x and y are not already in same set. Merge them.
			if (xRoot.rank < yRoot.rank) {
				xRoot.parent = yRoot;
			} else if (xRoot.rank > yRoot.rank) {
				yRoot.parent = xRoot;
			} else {
				yRoot.parent = xRoot;
				xRoot.rank = xRoot.rank + 1;
			}

		}

		private static class UnionSetElement<T> {
			public UnionSetElement<T> parent;
			public int rank;
			public T data;
		}

	}
}