题意：一张图上分布着n台坏了的电脑，并知道它们的坐标。两台修好的电脑如果距离<=d就可以联网，也可以通过其他修好的电脑间接相连。给出操作“O x”表示修好x，给出操作“S x y”，请你判断x和y在此时有没有连接上。
思路：并查集
AC代码：
#include <iostream> #include <iomanip> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> using namespace std; int dis; int x[1002][1002]; int y[1002][1002]; int pre[20000],v[20000]; struct point { int x; int y; }p[1002]; int distance(int a,int b,int c,int d) { if(((a-c)*(a-c)+(b-d)*(b-d))<=(dis*dis)) return true; else return false; } int find(int x) { if(pre[x]==x) return x; else { int a=find(pre[x]); pre[x]=a; return pre[x]; } } bool same(int a,int b) { return find(a)==find(b); } void unite(int a,int b) { int c=find(a); int d=find(b); if(c!=d)// 注意！！合并的是啥？父集！！ pre[d]=c; // if(!same(a,b))//XXXXX错 // { // pre[a]=b; // pre[b]=a; // } } int main() { int n,a,b; cin>>n>>dis; for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); } for(int i=1;i<=n;i++) { pre[i]=i; v[i]=0; } char s; while(cin>>s)//此处scanf超时 { if(s=='O') { cin>>a; v[a]=1; for(int i=1;i<=n;i++) { if(i!=a&&v[i]&&distance(p[a].x,p[a].y,p[i].x,p[i].y))//注意！！要有v[i]!=0这个条件否则将没修好的电脑也算上了 unite(a,i); } } else if(s=='S') { cin>>a>>b; if(same(a,b)) cout<<"SUCCESS"<<endl; else cout<<"FAIL"<<endl; } } }
