codeforces 217A. Ice Skating DFS or 并查集

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

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

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

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

或者直接裸并查集。

DFS

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

并查集

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

最后

以上就是苹果项链为你收集整理的codeforces 217A. Ice Skating DFS or 并查集的全部内容，希望文章能够帮你解决codeforces 217A. Ice Skating DFS or 并查集所遇到的程序开发问题。

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