Codeforces Round #134 (Div. 1) A : Ice Skating

問題概要

平面上にN(<100)個の点がある。x座標かy座標が等しい2点の間に辺をはることによってグラフを連結にしたい。最小いくつ点を追加すればよいか求める問題。

解法

一つの点を置くことによって3つ以上の連結成分をつなげることはできないので、追加前の連結成分の個数を数えるだけでよい。

acceptされたコード

UnionFind uf;

const int MAX_N = 100;

int N;
int xs[MAX_N], ys[MAX_N];

void init() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d%d", xs+i, ys+i);
	}
}

int solve() {
	uf.init(N);
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (xs[i] == xs[j] || ys[i] == ys[j]) {
				uf.merge(i, j);
			}
		}
	}
	int ans = -1;
	for (int i = 0; i < N; ++i) {
		if (uf.getRoot(i) == i) {
			++ans;
		}
	}
	return ans;
}

int main() {
	init();
	printf("%d\n", solve());
	return 0;
}