UVa 793 - Network Connections

// UVa 793 - Network Connections
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try (Scanner scanner = new Scanner(System.in)) {
			int cases = scanner.nextInt();
			for (int caseCounter = 1; caseCounter <= cases; caseCounter++) {

				int numberOfComputers = scanner.nextInt();
				scanner.nextLine();

				UnionSet<Integer> unionSet = new UnionSet<Integer>();
				for (int i = 1; i <= numberOfComputers; i++)
					unionSet.makeSet(i);

				int yes = 0, no = 0;
				while (scanner.hasNextLine()) {
					String line = scanner.nextLine();
					if (line.length() == 0)
						break;
					String[] tokens = line.split(" ");
					String operationType = tokens[0];
					int a = Integer.parseInt(tokens[1]);
					int b = Integer.parseInt(tokens[2]);

					if ("c".equalsIgnoreCase(operationType)) {
						unionSet.union(a, b);
					} else if ("q".equalsIgnoreCase(operationType)) {
						if (unionSet.areOnSameSet(a, b))
							yes++;
						else
							no++;
					}
				}

				if (caseCounter > 1)
					System.out.println();
				System.out.println(yes + "," + no);
			}
		}
	}

	public static class UnionSet<T> {

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

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

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

		public boolean areOnSameSet(T a, T b) {
			UnionSetElement aElement = dataToElement.get(a);
			UnionSetElement bElement = dataToElement.get(b);
			return find(aElement) == find(bElement);
		}

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

		private static UnionSetElement createElement() {
			UnionSetElement element = new UnionSetElement();
			element.parent = element;
			element.rank = 0;
			return element;
		}

		private static UnionSetElement find(UnionSetElement element) {
			if (element.parent != element) {
				element.parent = find(element.parent);
			}
			return element.parent;
		}

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

			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 {
			public UnionSetElement parent;
			public int rank;
		}

	}

}