/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:梁岳传
//作品时间:2008-8-16
//最后修改:2008-8-16
//Q Q 号码:280282813
//版权所有,翻版必究
////////////////////////////////////////

#include<iostream>
#include<cmath>
using namespace std;
typedef struct
{
    int x;
    int y;
    int parent;
}Node;
class Set
{
    public:
        Node* ary;
        int length;
    public:
        int Find(int index);
        bool Union(int first, int second);
        Set(int n);
        virtual ~Set(){delete[]ary;}
};

Set::Set(int n)
{
    int i;
    ary = new Node[n+10];
    length = n;
    for(i = 1; i <= n; ++i)
    {
        cin>>ary[i].x>>ary[i].y;
        ary[i].parent = -1;
    }
}
//将每次查找过的路线上的结点全部都指向根结点
int Set::Find(int index)
{
    int i, j, t;
    if(index <= 0 || index > length) return -1;

//查找index元素的根结点
    for(i = index; ary[i].parent > 0; i = ary[i].parent);
//将这条路线上的所有元素全部指向根结点
    for(j = index; j != i; j = t){
        t = ary[j].parent;
        ary[j].parent = i;
    }
    return i;
}
//树的根结点保存树的元素个数,以负值的形式保存
bool Set::Union(int first, int second)
{
    int i, j;
    if(first <= 0 || first > length)
        return false;
    if(second <= 0 || second > length)
        return false;
//寻找两个元素所在树的根结点
    i = Find(first);
    j = Find(second);

//越过边界或者两个元素已经在同一棵树中
    if(i == j)
        return false;

//如果第i棵树的元素比第j棵树的元素要多则将j加入到i中
    if(ary[i].parent < ary[j].parent){
        ary[i].parent += ary[j].parent;
        ary[j].parent = i;
    }
//否则将i加入到j中
    else{
        ary[j].parent += ary[i].parent;
        ary[i].parent = j;
    }
    return true;
}
int main(int argv, char* argc[])
{
    int num, dmax, ct;
    char ch;
    int i, first, second;
    int que[1100];
    cin>>num>>dmax;
    Set set(num);
    ct = 0;
    getchar();
    while(scanf("%c", &ch) != EOF){
        if(ch == 'O'){
            scanf("%d", &first);
            que[ct] = first;
 
            for(i = 0; i < ct; ++i){
                if(sqrt((double)(set.ary[que[i]].x-set.ary[first].x)*(set.ary[que[i]].x-set.ary[first].x) \
                    +(set.ary[que[i]].y-set.ary[first].y)*(set.ary[que[i]].y-set.ary[first].y)) <= dmax)
                set.Union(first, que[i]);
            }
            ct++;
        }
        else{
            scanf("%d%d", &first, &second);
            if(set.Find(first) == set.Find(second))
                cout<<"SUCCESS"<<endl;
            else cout<<"FAIL"<<endl;
        }
        getchar();
    }
    return 0;
}

评论