Codeforces 217A Ice Skating 题解

100 阅读 0 评论 66 点赞

我是靠谱客的博主花痴鞋垫，最近开发中收集的这篇文章主要介绍Codeforces 217A Ice Skating 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意

一个人滑冰，只能沿平行于坐标轴的方向直线滑冰，遇到雪堆才能停下来，问最少需要再增加多少雪堆才能使得他可以到达任意一个雪堆

思路

并查集，如果两个雪堆有一维坐标相同那就把他们所在的集合合并，最后的答案就是集合数减1

代码

#include <cstdio>
int father[101];
int x[101],y[101];
int findfather(int x)
{
if(father[x]==x)
return x;
else return father[x]=findfather(father[x]);
}
int main()
{
int n,ans;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(x[i]==x[j]||y[i]==y[j])
father[findfather(i)]=findfather(j);
ans=0;
for(int i=1;i<=n;i++)
if(father[i]==i)
ans++;
printf("%dn",ans-1);
return 0;
}