POJ 2236

继续并查集，速度不怎么样，也没想到什么好的方法。

Problem:		User:
Memory: 180K		Time: 1266MS
Language: C++		Result: Accepted

#include <iostream>
using namespace std;

const int MAX=1005;
bool OK[MAX];
int X[MAX];
int Y[MAX];
int R[MAX];
int P[MAX];
int N,D;
int Find(int id)//查找 递归路径压缩

{
    if(P[id]!=id)
        P[id]=Find(P[id]);
    return P[id];
}
void Union(int x,int y)
{
    int r1=Find(x);
    int r2=Find(y);
    if(r1==r2)
        return;
    if(R[r1]>R[r2])
        P[r2]=r1;
    else
    {
        P[r1]=r2;
        if(R[r2]==R[r1])
            ++R[r2];
    }
}

int len(int i,int j)
{
    int x_diff=abs(X[i]-X[j]);
    int y_diff=abs(Y[i]-Y[j]);
    return x_diff*x_diff+y_diff*y_diff;
}

void Make_set()
{
    //make set;

    for(int i=0;i<=N;i++)
    {
        P[i]=i;
        R[i]=0;
    }
}

int main()
{
    char Op;
    int a,b;
    memset(OK,false,sizeof(OK));
    scanf("%d %d",&N,&D);
    int limit=D*D;
    for(int i=1;i<=N;i++)
        scanf("%d %d",&X[i],&Y[i]);
    Make_set();
    while(scanf("%c",&Op)!=EOF)
    {
        if(Op=='O'){
            scanf("%d",&a);
            OK[a]=true;
            for(int i=1;i<=N;i++)
            {
                if(i==a)
                    continue;
                else if(OK[i]&&(len(a,i)<=limit))
                    Union(a,i);
            }
        }
        else if(Op=='S'){
            scanf("%d %d",&a,&b);
            if(OK[a]&&OK[b]
               &&(Find(a)==Find(b)))
            {
                //cout<
                printf("SUCCESS\n");
            }
            else
                printf("FAIL\n");
        }
    }
    return 0;
}