题目链接
题意：
有n台电脑，x,y代表电脑坐标 ，两台修好的电脑如果距离<=d就可以联网， O p 代表 修理p电脑 S p q代表链接p q
题解：
并查集维护即可，在O操作下，在已经修好的电脑里面找到与当前电脑距离<=d 的，join()一下
代码：
#include<iostream> #include<stdio.h> #include<math.h> using namespace std; typedef long long ll; const int maxn=5e5+5; int f[maxn]; int n,d; int dx[maxn],dy[maxn]; int tmp[maxn]; int Find(int x) { return x==f[x]?x:f[x]=Find(f[x]); } void join(int x,int y) { int fx=Find(x); int fy=Find(y); if(fx!=fy) { f[fx]=fy; } } double dis(int a,int b) { return sqrt((double)((dx[a]-dx[b])*(dx[a]-dx[b])+(dy[a]-dy[b])*(dy[a]-dy[b]))); } int main() { scanf("%d%d",&n,&d); for(int i=1;i<=n;i++)scanf("%d%d",&dx[i],&dy[i]); for(int i=1;i<=n;i++)f[i]=i; char op; int p,q; int cnt=0; while(cin>>op) { if(op==‘O‘) { scanf("%d",&p); tmp[cnt++]=p; for(int i=0;i<cnt;i++) { if(dis(tmp[i],p)<=(double)d)join(tmp[i],p); } } else { scanf("%d%d",&p,&q); if(Find(p)==Find(q))printf("SUCCESS\n"); else printf("FAIL\n"); } } return 0; }
原文：https://www.cnblogs.com/j666/p/11609973.html
