C - Ice Skating CodeForces - 217A

62 阅读 0 评论 41 点赞

我是靠谱客的博主称心方盒，最近开发中收集的这篇文章主要介绍C - Ice Skating CodeForces - 217A，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

C - Ice Skating

CodeForces - 217A

Bajtek is learning to skate on ice. He's a beginner, so his only mode of transportation is pushing off from a snow drift to the north, east, south or west and sliding until he lands in another snow drift. He has noticed that in this way it's impossible to get from some snow drifts to some other by any sequence of moves. He now wants to heap up some additional snow drifts, so that he can get from any snow drift to any other one. He asked you to find the minimal number of snow drifts that need to be created.

We assume that Bajtek can only heap up snow drifts at integer coordinates.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 100) — the number of snow drifts. Each of the following n lines contains two integers xi and yi (1 ≤ xi, yi ≤ 1000) — the coordinates of the i-th snow drift.

Note that the north direction coinсides with the direction of Oy axis, so the east direction coinсides with the direction of the Ox axis. All snow drift's locations are distinct.

Output

Output the minimal number of snow drifts that need to be created in order for Bajtek to be able to reach any snow drift from any other one.

Examples

input

Copy
2
2 1
1 2

output
1

input

Copy
2
2 1
4 1

output
0

题意：重点需要理解里面是雪堆，是可以重复使用的……

例如（1,1）（1,2）（2,1）三个点，从（1,1）开始遍历花费是0，从（1,2）开始遍历花费也是0.

为什么要强调这一点呢……因为模拟赛的时候，我以为只能使用一次，所以在我看来（1,2）开始遍历花费是0，（1,1）开始花费就是1。_(:з」∠)_一坑坑全队，队友都被我带偏了，一道简单题没拿下来

思路：任意选一点，标记它0花费的点，所有被标记的都递归延伸直到无法标记为止。如果这时还有未被标记的点，则再其中任意挑一个重复上面步骤，同时结果result +1，最后输出result即可。用dfs也可以实现，我用的是并查集+最小生成树

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int num[1010]={0};// 记录是否使用过
int map[1010][1010];// 记录点
struct node{
int x;int y;
node(int a,int b){
x = a; y = b;
}
};
vector<node> v;
queue<node> q;
int check(int n){
for(int i=1;i<=n;i++)
if(!num[i]) return i;
return 0;
}
void work(){
while(q.size()){
node tmp = q.front();
q.pop();
int t;
for(int i=1;i<=1000;i++){
t = map[tmp.x][i];//map 上的值是唯一标记，且与vector上对应
if(t && !num[t]){
q.push(v[t]);
num[t] = 1;
}
t = map[i][tmp.y];
if(t && !num[t]){
q.push(v[t]);
num[t] = 1;
}
}
}
}
int main(){
int n;
cin>>n;
int a,b,t;
v.push_back(node(0,0));//下面从一开始计数
for(int i=1;i<=n;i++){
cin>>a>>b;
v.push_back(node(a,b));
map[a][b] = i;
}
t=check(n);
int cnt=-1;
while(t){
cnt++;
q.push(v[t]);
num[t] = 1;
work();
t=check(n);
}
cout<<cnt<<endl;
}