首页 > 分享 > CF217A Ice Skating 解题报告

CF217A Ice Skating 解题报告

花匠小妙招
2026-04-29 04:06

CF217A Ice Skating 解题报告

1 题目链接

https://codeforces.com/problemset/problem/217/A

2 题目整理

题目：滑冰

题目描述

巴伊泰克正在学习在冰上滑冰。他是一个初学者，所以他唯一的交通方式就是从一个雪堆向北、向东、向南或向西滑行，直到他降落在另一个雪堆上。他注意到，用这种方法是不可能从一堆雪堆移动到另一堆雪堆的。现在他想再堆一些雪堆，这样他就可以从任何一个雪堆堆到其他任何一个。他要求你找出需要建造的最小数量的雪堆。

我们假设Bajtek只能在整数坐标上堆积雪堆。

输入格式

第一行包含一个整数 n n n,表示雪堆的个数。

接下来 n n n行每行两个整数 x i , y i x_i, y_i xi,yi,表示第 i i i个雪堆的坐标。

输出格式

输出一行一个整数，表示需要额外建立的雪堆数量。

样例输入1

2 2 1 1 2 123 样例输出1

1 1 样例输入2

2 2 1 4 1 123 样例输出2

0 1 数据范围

对于 100 % 100% 100%的数据:

1 ≤ n ≤ 100 1 leq n leq 100 1≤n≤100 1 ≤ x i , y i , ≤ 1000 1 leq x_i, y_i, leq 1000 1≤xi,yi,≤1000 3 题意分析 3.1 题目大意

有一个人，他只能在雪堆调整方向，直到到达另一个雪堆。请问最少需要额外建立多少个雪堆，才能使这个人能从任意一个雪堆到达另一个雪堆。

3.2 样例分析

如上所述。

4 解法分析

这道题是一道建图+并查集的简单题目。

首先，由题意可知，这个人只能在雪堆改变方向。所以，同行同列的两个雪堆这个人是一定能互相到达的。那么，根据这个规则，我们可以用并查集来建图。此时，这个图会存在着 p p p个连通块。这个时候，如果想让这个图连通，就至少需要增加 p − 1 p-1 p−1个雪堆。

再提一点，这题中的并查集是可以用dfs或bfs来平替的。

A C代码 ACCode #001

// From djq_cpp // Rating 3180 // reason : 思路清晰，代码简洁明了，运用了vector来储存图， #include <iostream> #include <vector> using namespace std; int x[100],y[100]; vector <int> nt[100]; bool v[100]; void dfs(int ns) {v[ns]=true;for(int k=0;k<(int)nt[ns].size();k++)if(!v[nt[ns][k]])dfs(nt[ns][k]); } int main() {int n,cnt=0;cin>>n;for(int i=0;i<n;i++){cin>>x[i]>>y[i];for(int j=0;j<i;j++)if(x[i]==x[j]||y[i]==y[j]){nt[i].push_back(j);nt[j].push_back(i);}}for(int k=0;k<n;k++)if(!v[k]){dfs(k);cnt++;}cnt--;cout<<cnt;return 0; }

cpp

运行

12345678910111213141516171819202122232425262728293031323334353637383940 ACCode #002

// From xlk // Rating 2428 // reason : 思路清晰，代码简洁明了，运用了并查集 #include <bits/stdc++.h> using namespace std; int n, c; int x[120]; int y[120]; int f[120]; int F(int x) {return f[x] != x ? f[x] = F(f[x]) : x; } void U(int x, int y) {x = F(x);y = F(y);if (x != y){f[x] = y;c--;} } int main() {cin >> n;for (int i = 0; i < n; i++){cin >> x[i] >> y[i];f[i] = i;}c = n;for (int i = 0; i < n; i++){for (int j = 0; j < i; j++){if (x[i] == x[j] || y[i] == y[j]){U(i, j);}}}cout << c - 1 << endl;return 0; }

cpp

运行

12345678910111213141516171819202122232425262728293031323334353637383940414243444546 ACCode #003

// From Heart_Blue // Rating 2425 // reason : 思路清晰，代码简洁明了，运用了Class和并查集 #include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <numeric> #include <iomanip> #include <bitset> #include <list> #include <stdexcept> #include <functional> #include <utility> #include <ctime> using namespace std; typedef long long LL; typedef unsigned long long ULL; #define MAX(a,b) ((a) > (b) ? (a) : (b)) #define MIN(a,b) ((a) < (b) ? (a) : (b)) #define MEM(a,b) memset((a),(b),sizeof(a)) const LL INF = 1e9 + 7; const int N = 2e2 + 10; int x[N], y[N]; class UnionFind { private:int p[N]; public:int size(int x){int px = Find(x);return -p[px];}void init(){MEM(p, -1);}int Find(int x){int root = x;while (p[root] >= 0) root = p[root];while (x != root){int tmp = p[x];p[x] = root;x = tmp;}return root;}void Union(int x, int y){int px = Find(x);int py = Find(y);if (size(px) > size(py)) swap(px, py);int total = size(px) + size(py);p[px] = py;p[py] = -total;} } uf; int main() {//freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);uf.init();int n;cin >> n;for (int i = 0; i < n; i++){cin >> x[i] >> y[i];}int ans = n - 1;for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){if (x[i] != x[j] && y[i] != y[j]) continue;if (uf.Find(i) != uf.Find(j)){uf.Union(i, j);ans--;}}}cout << ans << endl;return 0; }

cpp

运行

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798