#include<cstdio>
#include<fstream>
#include<vector>
using namespace std;

struct co
{
long long int x;
long long int y;
};

class UFset
{
public:
        UFset(int s) ;
	int find(int i);
	void unionset(int root1,int root2);
private:
int size;
int* parent;
};
//-----------------------------------------
UFset :: UFset ( int s ) 
{   size = s;					
    parent = new int [size+1];
    for ( int i = 0; i <= size; i++ ) parent[i] = -1;
    return;
}

//-----------------------------------------
int UFset::find(int i)
{
    int j;
    for ( j = i; parent[j] >= 0; j = parent[j]);
    while ( i != j )       
    { 
        int temp = parent[i];
        parent[i] = j;
        i = temp;
    }
    return j;
}

//------------------------------------------
void UFset:: unionset(int root1,int root2)
{
    int temp = parent[root1] + parent[root2];
    if ( parent[root2] < parent[root1] )
    {
        parent[root1] = root2;      
        parent[root2] = temp;
    }
    else 
    {
        parent[root2] = root1;      
        parent[root1] = temp;       
    }
	return;
}
//=======================================================




int main()
{
       // freopen("in.txt","r",stdin);
	int n,i,j;
        long long int d;
        scanf("%d%LLd",&n,&d);
	vector<co> data(n+1);
	for( i=1;i<=n;i++)
		scanf("%LLd%LLd",&data[i].x,&data[i].y);
        vector<bool> pa(n+1,0);
        UFset  com(n);
	char c;
	int num1,num2;
	while(scanf("%c",&c)==1)
	{
	    if(c=='O')
            {
                scanf("%d",&num1);
                pa[num1]=1;
                for(j=1;j<=n;j++)
                {
                    if(j==num1) continue;
                    long long int temp=(data[num1].x-data[j].x)*(data[num1].x-data[j].x)+(data[num1].y-data[j].y)*(data[num1].y-data[j].y);
                    if(temp<=d*d&&pa[j]) com.unionset(com.find(num1),com.find(j));
                }
            }
            else if(c=='S')
		{
                    scanf("%d%d",&num1,&num2);
                    if(num1==num2)
                    {
                        if(pa[num1]) printf("SUCCESS\n"); else printf("FAIL\n");
                    }
                    else if(com.find(num1)==com.find(num2)) printf("SUCCESS\n"); else printf("FAIL\n");
		}
	}

	return 0;
}

• 并查集的合并操作错了 (3012) xfxyjwf 2006-05-04 02:40:35
  • Re:并查集的合并操作错了 (18) laddiexu 2006-05-04 12:57:28