///////////////////////////////////////////作品名称:并查集应用//作者姓名:梁岳传//作品时间: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;}

评论