无线网络

题意描述

东南亚发生地震。ACM（亚洲合作医疗队）已经搭载了膝上型计算机的无线网络，但意外的余震遭到袭击，网络中的所有计算机都被破坏。电脑逐一修复，网络逐渐开始重新工作。由于硬件限制，每台计算机只能直接与距离它不远的计算机进行通信。但是每个计算机都可以被视为两台计算机之间的通信中介，也就是说计算机A和计算机B可以通信，如果计算机A和计算机B可以直接通信，或者有一个计算机C可以与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。
“S p q”（1 <= p，q <= N），这意味着测试计算机p和q是否可以通信。

输入不超过30万行。

产量

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

样品输入

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<cstdio>
#include<cstring>
int n,d,p[1010];
bool vis[1010];
int map[1010][1010];
struct node
{
    int x,y;
}a[1010];
void init()
{
    for(int i=1;i<=n;i++)  p[i]=i;
}
int getfather(int x)
{
    if(x!=p[x]) p[x]=getfather(p[x]);
    return p[x];
}
void Union(int a,int b)
{
    a=getfather(a);
    b=getfather(b);
    p[a]=b;
}
int cal(int i,int j)
{
    return((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
int main()
{
        scanf("%d%d",&n,&d);
        d=d*d;
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
        init();
        for(int i=1;i<n;i++)
          for(int j=i;j<=n;j++)
          if(i==j) map[i][j]=map[j][i]=0;
          else map[i][j]=map[j][i]=cal(i,j);
        char str[10];
        while(scanf("%s",str)!=EOF)
        {
            if(str[0]=='O')
            {
                int x;
                scanf("%d",&x);
                if(!vis[x])
                {
                    vis[x]=true;
                    int a=getfather(x);
                    for(int i=1;i<=n;i++)
                    if(i!=x&&vis[i]&&(getfather(i)==a || map[i][x]<=d)) Union(i,x);
                }
            }
            else
            {
                int x,y;
                scanf("%d%d",&x,&y);
                if(vis[x]&&vis[y])
                {
                    int a=getfather(p[x]);
                    int b=getfather(p[y]);
                    if(a==b) printf("成功");
                    else printf("失败");
                }
                else printf("失败");
            }
        }
    return 0;
}

测试截图