codeforces 217A. Ice Skating DFS or 并查集

87 阅读 0 评论 58 点赞

我是靠谱客的博主苹果项链，这篇文章主要介绍codeforces 217A. Ice Skating DFS or 并查集，现在分享给大家，希望可以做个参考。

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

坐标上n个点，从每个点四个方向可以飘到下一个点为止，求需要再多增加几个点，使得我们能从一个点飘到任意其他点。

把能够互相到达的点视为一个集合，即求集合的数量-1.

刚开始的DFS很失败，应该直接比较两点的x和y，而不是从一个点慢慢+1+1去判断该点是否有雪堆。

或者直接裸并查集。

DFS

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1005;
const int INF=1<<30;
int x[maxn];
int y[maxn];
int n;
bool vis[maxn];
void dfs(int u){
vis[u]=1;
for (int i=0;i<n;i++){
if ((x[i]==x[u]||y[i]==y[u])&&!vis[i]){
dfs(i);
}
}
}
int main(){
cin >> n;
for (int i=0;i<n;i++){
cin >> x[i] >> y[i];
}
int ans=0;
for (int i=0;i<n;i++){
if (!vis[i]){
ans++;
dfs(i);
}
}
cout << ans-1 << endl;
}

并查集

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1005;
const int INF=1<<30;
int fa[maxn];
int x[maxn];
int y[maxn];
int n;
void init(){
for (int i=0;i<n;i++){
fa[i]=i;
}
}
int find(int x){
if (x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void unite(int x,int y){
x=find(x);
y=find(y);
if (x==y) return;
fa[y]=x;
}
int main(){
cin >> n;
for (int i=0;i<n;i++){
cin >> x[i] >> y[i];
}
init();
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (x[i]==x[j]||y[i]==y[j]){
unite(i,j);
}
}
}
int ans=0;
for (int i=0;i<n;i++){
if (fa[i]==i) ans++;
}
cout << ans-1 << endl;
}