并查集kuangbin带你飞合集

 1 #include
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 const int maxn=1100;
 7 int n,d;
 8 struct point{
 9     int x,y;
10 };
11 point pt[2010];
12 char cr;
13 int a,b;
14 int f[2010];
15 int vis[2010];
16 
17 int find(int k){
18    if(f[k]==-1) return k;
19    else return f[k]=find(f[k]);    
20 }
21 
22 bool join(int s,int e){
23     return (pt[s].x-pt[e].x)*(pt[s].x-pt[e].x)+(pt[s].y-pt[e].y)*(pt[s].y-pt[e].y)<=d*d;
24 }
25 
26 int main(){
27     scanf("%d%d",&n,&d);
28     for(int i=1;i<=n;i++) scanf("%d%d",&pt[i].x,&pt[i].y);
29     for(int i=1;i<=n;i++) f[i]=-1;
30     memset(vis,0,sizeof(vis));
31     while(scanf("\n%c",&cr)!=EOF){
32         if(cr==‘S‘){
33             scanf("%d%d",&a,&b);
34             int t1=find(a),t2=find(b);
35             if(t1!=t2) printf("FAIL\n");
36             else printf("SUCCESS\n");
37         }else{
38             scanf("%d",&a);
39             vis[a]=1;
40             for(int i=1;i<=n;i++){
41                 if(vis[i]==1&&i!=a){
42                     int t1=find(i),t2=find(a);
43                     if(t1==t2) continue;
44                     if(join(i,a)) f[t1]=t2;
45                 }
46             }
47         }
48     }
49     return 0;
50 }