并查集-E - Wireless Network

E - Wireless Network

 #include<iostream>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int x[], y[];//存放电脑的横纵坐标

 int dis[][];//存放电脑i和电脑j之间的距离

 int parent[];//并查集的关系联系数组

 int n, d, a, b;

 int is[];//判断电脑是否已修复

 char ask[];

 void init(int n){//联系数组初始化

     for(int i=; i<=n; i++)

         parent[i] = i;

 }

 int find(int x){

     if(x == parent[x])

         return x;

     return parent[x] = find(parent[x]);

 }

 void unionit(int a, int b){

     int fa = find(a);

     int fb = find(b);

     parent[fb] = fa;

 }

 int main(){

     scanf("%d %d", &n, &d);

     for(int i=; i<=n; i++){

         scanf("%d %d",x+i, y+i);

         is[i] = ;

     }

     for(int i=; i<=n; i++)//求两电脑间距离

         for(int j=i+; j<=n; j++)

             dis[i][j] = dis[j][i] = (x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]);//此处求出的距离未开根

     init(n);

     while(~scanf("%s",ask)){

         if(ask[] == 'O'){

             scanf("%d",&a);

             if(is[a])    continue;//若电脑已修复，则没必要进行下面操作

             is[a] = ;

             for(int i=; i<=n; i++)//逐一遍历，找到在可连接范围内的电脑并与之联系

                 if(is[i] && dis[i][a] <= d*d)

                     unionit(i, a);

         }else{

             scanf("%d %d",&a, &b);

             if(find(a) == find(b))//判断两台电脑是否可相互联系

                 printf("SUCCESS\n");

             else

                 printf("FAIL\n");

         }

     }

     return ;

 }