题意:有很多无线电站台分别位于平面的坐标上,可以直接联系或间接联系,直接联系即两点距离小于等于d,间接联系就是通过其他电台联系,初始所有电台都是坏的,给出一系列操作,修复某电台,以及询问某两座电台是否能够联系。
先根据各个电台的坐标建立修复后可以直接联系的边,然后每修好一个,就遍历与它可以直接联系的电台,若也是修好的就合并并查集。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6
7 int xx[1005],yy[1005];
8 int fa[1005],n;
9 bool vis[1005];
10 int head[1005],point[1005*1005],nxt[1005*1005],size;
11
12 void add(int a,int b){
13 point[size]=b;
14 nxt[size]=head[a];
15 head[a]=size++;
16 }
17
18 void init(){
19 for(int i=1;i<=n;i++)fa[i]=i;
20 }
21
22 int find(int x){
23 int r=x,t;
24 while(r!=fa[r])r=fa[r];
25 while(x!=r){
26 t=fa[x];
27 fa[x]=r;
28 x=t;
29 }
30 return r;
31 }
32
33 int main(){
34 int d;
35 scanf("%d%d",&n,&d);
36 int i,j;
37 memset(head,-1,sizeof(head));
38 size=0;
39 for(i=1;i<=n;i++){
40 scanf("%d%d",&xx[i],&yy[i]);
41 for(j=1;j<i;j++){
42 if((xx[i]-xx[j])*(xx[i]-xx[j])+(yy[i]-yy[j])*(yy[i]-yy[j])<=d*d){
43 add(i,j);
44 add(j,i);
45 }
46 }
47 }
48 init();
49 char s[10];
50 while(scanf("%s",s)!=EOF){
51 if(s[0]=='O'){
52 int a;
53 scanf("%d",&a);
54 vis[a]=1;
55 for(i=head[a];~i;i=nxt[i]){
56 int j=point[i];
57 if(vis[j]){
58 int x=find(a),y=find(j);
59 if(x!=y)fa[x]=y;
60 }
61 }
62 }
63 else if(s[0]=='S'){
64 int a,b;
65 scanf("%d%d",&a,&b);
66 int x=find(a),y=find(b);
67 if(x==y)printf("SUCCESS
");
68 else printf("FAIL
");
69 }
70 }
71 }