TopCoder SRM 640 Div1 Easy: ChristmasTreeDecoration

解法

na-o-s.hateblo.jp

コード

public class ChristmasTreeDecoration {

	public int solve(int[] col, int[] x, int[] y) {
		int N = col.length;
		UnionFind uf = new UnionFind(N);
		for (int i = 0; i < y.length; i++) {
			if (col[x[i] - 1] != col[y[i] - 1]) {
				uf.unite(x[i] - 1, y[i] - 1);
			}
		}

		int groups = 1;
		for (int i = 0; i < N; i++) {
			if (!uf.isSame(0, i)) {
				groups++;
				uf.unite(0, i);
			}
		}

		return groups - 1;
	}

	class UnionFind {
		int[] parts;

		UnionFind(int n) {
			parts = new int[n];
			for (int i = 0; i < n; i++)
				parts[i] = i;
		}

		public int find(int x) {
			if (parts[x] == x)
				return x;
			return parts[x] = find(parts[x]);
		}

		public Boolean isSame(int x, int y) {
			return find(x) == find(y);
		}

		public void unite(int x, int y) {
			if (find(x) == find(y))
				return;
			parts[find(x)] = find(y);
		}
	}

}