无线网络 POJ - 2236

翻译：

地震发生在东南亚。ACM（亚洲合作医疗团队）已经与膝上电脑建立了无线网络，但是一次意外的余震袭击，网络中的所有计算机都被打破了。计算机一个接一个地修复，网络逐渐开始工作。由于硬件限制，每台计算机只能直接与距离它不远的计算机进行通信。但是，每台计算机都可以被视为两台其他计算机之间通信的中介，也就是说，如果计算机A和计算机B可以直接通信，或者计算机C可以与A和A进行通信，则计算机A和计算机B可以进行通信。

在修复网络的过程中，工作人员可以随时进行两种操作，修复计算机或测试两台计算机是否可以通信。你的工作是回答所有的测试操作。 

输入

第一行包含两个整数N和d（1 <= N <= 1001,0 <= d <= 20000）。这里N是计算机的数量，编号从1到N，D是两台计算机可以直接通信的最大距离。在接下来的N行中，每行包含两个整数xi，yi（0 <= xi，yi <= 10000），这是N台计算机的坐标。从第（N + 1）行到输入结束，存在逐个执行的操作。每行包含以下两种格式之一的操作： 
1。“O p”（1 <= p <= N），表示修复计算机p。 
2.“S p q”（1 <= p，q <= N），这意味着测试计算机p和q是否可以通信。 

输入不会超过300000行。 

产量

对于每个测试操作，如果两台计算机可以通信则打印“SUCCESS”，否则打印“FAIL”。

样本输入

4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4

样本输出

失败
成功

#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
#define MAXN 1010
 
int dx[MAXN],dy[MAXN];    //坐标
int par[MAXN];    //par[x]表示x的父节点
int repair[MAXN] ={0};
int n;


/*并查集三件套*/ 
void Init()    //初始化
{
    int i;
    for(i=0;i<=n;i++)
        par[i] = i;
}
int Find(int x)    //查询x的根节点并路径压缩
{
    if(par[x]!=x)
        par[x] = Find(par[x]);  //路径压缩
    return par[x];
}
void Union(int x,int y)    //合并x和y所在集合
{
    par[Find(x)] = Find(y);
}
 
int Abs(int n)  //绝对函数
{
    return n>0?n:-n;
}
 
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()
{
    int d,i;
 
    //初始化
    scanf("%d%d",&n,&d);
    Init();
 
    //输入坐标
    for(i=0;i<n;i++){
        scanf("%d%d",&dx[i],&dy[i]);
    }
    
    //操作
    char cmd[2];
    int p,q,len=0;
    while(scanf("%s",cmd)!=EOF){
        switch(cmd[0]){
        case 'O':
            scanf("%d",&p);
            p--;
            repair[len++] = p;
            for(i=0;i<len-1;i++)    //遍历所有修过的计算机，看能否联通
                if( repair[i]!=p && Dis(repair[i],p)<=double(d) ) //没修过的，但是距离近的
                    Union(repair[i],p);
            break;
        case 'S':
            scanf("%d%d",&p,&q);
            p--,q--;
            if(Find(p)==Find(q))    //是否有路
                printf("SUCCESS\n");
            else 
                printf("FAIL\n");
        default:
            break;
        }
    }
 
    return 0;
}