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; }