CF217A Ice Skating 解题报告

CF217A Ice Skating 解题报告

1 题目链接

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

2 题目整理

题目 ：滑冰

题目描述

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

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

输入格式

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

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

输出格式

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

样例输入1

2
2 1
1 2

样例输出1

1

样例输入2

2
2 1
4 1

样例输出2

0

数据范围

对于$100\%$的数据:

• $1\le n\le 100$
• $1\le x_i,y_i,\le 1000$

3 题意分析

3.1 题目大意

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

3.2 样例分析

如上所述。

4 解法分析

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

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

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

AC代码

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

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

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

最后

以上就是大气黑裤为你收集整理的CF217A Ice Skating 解题报告的全部内容，希望文章能够帮你解决CF217A Ice Skating 解题报告所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。