poj2236 938ms 并查集

#include<cstdio>
using namespace std;
//把可以连通的放到一个集合，然后再判断两台机子是不是在一个集合
const int N = 1e4;
int father[N+5];
bool vis[N+5];
int d;
struct Node
{
    int x;
    int y;
} computers[N+5];
void init(int n)
{
    for(int i = 1; i<=n; ++i)
        father[i] = i;
}
int find(int x)
{
    return x==father[x]?x:father[x]=find(father[x]);
}
/*非递归写法
int find(int x)
{
    int root = x,tmp;
    while(x!=father[x])
    {
        x = father[x];
    }
    if(root!-x)
    {
        tmp = father[root];
        father[root] = x;
        root = tmp;
    }
    return x;
}*/
void _union(int a,int b)
{
    int x = find(a);
    int y = find(b);
    if(x!=y)
        father[x] = y;
}
bool dis(int a,int b)
{
    int x = computers[a].x-computers[b].x;
    int y = computers[a].y-computers[b].y;
    if(x*x+y*y>d*d)
        return false;
    return true;
}

int main()
{
    int n;
    int x,y;
    scanf("%d%d",&n,&d);
    init(n);
    for(int i = 1; i<=n; ++i)
        scanf("%d%d",&computers[i].x,&computers[i].y);
    getchar();
    int p;
    char c;
    while(~scanf("%c",&c))
    {
        if(c=='O')
        {
            scanf("%d",&p);
            vis[p] = true;
            for(int i = 1; i<=n; ++i)
                if(i!=p&&vis[i]&&dis(i,p))
                    _union(i,p);
        }
        else
        {
            scanf("%d%d",&x,&y);
            puts(find(x)==find(y)?"SUCCESS":"FAIL");
        }
        getchar();
    }
    return 0;
}