CodeForces 217A Ice Skating（并查集思路）

题目链接

题目大概意思就是 在坐标系上 给你 几个点坐标 看他们需要几个中间点能让他们每两个都能连成一条线！这每个点就和 并查集的里每个点很像 看有几个祖先 祖先减一就是 这题答案！
所以 这题完全不用用到神马 图的连通集来做（其实是我还没学，不会）
这个思路 也是 tyh学长 讲解的 很有道理 啊！然而 当我真正开始写的时候 还是遇到不少问题 请教了学长 毕竟不是纯并查集 第一次写这个 ，最后在我的思考与请教下AC了，虽然效率很低，不过还是很爽的。
1.首先，并查集都是单个点（数据）对应单个点（数据），而这个每个坐标有两个数据，所以就把每个坐标当做一个编号，从1到100（题目说坐标个数不超过100） 。
2.根据题意判断能不能连就看这个坐标，x,y是否和另一个有一个相同（这个好像没考虑x,y都相同的情况），有就用并查集的知识连接起来！成一条线！，用两个for就可以将每个点与其他点判断一次！

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int father[1001];
int findfather(int x)
{
if(father[x]==x)
return x;
else
{
father[x]=findfather(father[x]);
return
father[x];
}
}
void merge(int a,int b)
{
int fa=findfather(a);
int fb=findfather(b);
if(fa!=fb)
{
father[fb]=fa;
}
}
int main()
{
int n;
while(cin>>n&&n)
{
int x[n+1],y[n+1],t=0;
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[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])
{
merge(i,j);
}
}
}
for(int i=1;i<=n;i++)
{
if(father[i]==i)
t++;
}
cout<<t-1<<endl;
}
return 0;
}

后天就是校赛。。。真的很虚。。。最近效率还是很低。。。学业也忙起来了。。。心中还有别的事情牵绊。。。不多说 加油吧！~

最后

以上就是壮观冰棍为你收集整理的CodeForces 217A Ice Skating（并查集思路）的全部内容，希望文章能够帮你解决CodeForces 217A Ice Skating（并查集思路）所遇到的程序开发问题。

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