题意：有n台电脑，初始全部损坏。输入O：x，修理x号电脑。S：x，y询问x,y是否可以联系。两个电脑可以联系必须保证距离<=d，或者通过与它相连通的电脑来建立联系，但是这个距离是保证。
解析：修理一台电脑，就遍历其他电脑，如果满足距离<=d而且另一台电脑已被修理，就把它们放入同一集合。询问时查询两者父亲节点，一样就可以。注意FAIL，别输成FALL。。。
而且我加入了路径压缩和dis[][]后时间并没有多大改观，也就优化了几十秒。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int maxn=1111; bool vis[maxn]; int pr[maxn]; ll n,d; struct node { int x,y; }st[maxn]; void first() { memset(vis,false,sizeof(vis)); } int find(int x) { if(x!=pr[x]) pr[x]=find(pr[x]); return pr[x]; } void join(int x,int y) { int f1=find(x); int f2=find(y); if(f1!=f2) { pr[f1]=f2; } return ; } int main() { scanf("%lld%lld",&n,&d); first(); d=d*d; for(int i=1;i<=n;i++) { scanf("%d%d",&st[i].x,&st[i].y); pr[i]=i; } char ch; while(scanf("%c",&ch)!=EOF) { if(ch==‘\n‘) continue; if(ch==‘O‘) { int id; scanf("%d",&id); vis[id]=true; for(int i=1;i<=n;i++) { if(i!=id) { ll mid=(st[i].x-st[id].x)*(st[i].x-st[id].x)+(st[i].y-st[id].y)*(st[i].y-st[id].y); if(mid<=d&&vis[i]==true) { join(id,i); } } } } else { int id1,id2; scanf("%d%d",&id1,&id2); int f1=find(id1); int f2=find(id2); if(f1==f2) cout<<"SUCCESS"<<endl; else cout<<"FAIL"<<endl; } } }
原文：https://www.cnblogs.com/liyexin/p/12593489.html