Wireless Network

一道并查集模板题。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#define INF 0x3f3f3f3f
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int posx[1200],posy[1200];
int pre[1200];
int been[1200];
int findr(int x)
{
    if(x==pre[x])
        return x;
    return pre[x]=findr(pre[x]);
}
int dist(int ax,int ay,int bx,int by)
{
    return (ax-bx)*(ax-bx)+(ay-by)*(ay-by);
}
void rep(int i,int x,int n,int d)
{    
    int ri=findr(i);
    int rx=findr(x);
    if(dist(posx[x],posy[x],posx[i],posy[i])<=d*d)    
        pre[rx]=ri;
}
bool check(int a,int b)
{
    char ch;
    int ra=findr(a);
    int rb=findr(b);
    if(ra==rb)
        return true;
    return false;
}
int main()
{
    int n;
    int d;int p,q;
    char ch;
    while(scanf("%d %d",&n,&d)!=EOF)
    {
        int i;
        for(i=1;i<=n;i++)
            scanf("%d %d",&posx[i],&posy[i]);
        getchar();
        for(i=1;i<=n;i++)
            pre[i]=i;
        mst(been,0);
        while(cin>>ch)
        {
            if(ch=='O')
            {
                scanf("%d",&p);
                been[p]=1;
                for(i=1;i<=n;i++)
                {
                    if(been[i])
                        rep(i,p,n,d);
                }
            }
            if(ch=='S')
            {
                scanf("%d %d",&p,&q);
                if(check(p,q))
                    printf("SUCCESS\n");
                else
                    printf("FAIL\n");
            }
        }
    }
    return 0;
}