整个程序三个问题:
1.并查集的合并操作不对
2.输入字符时处理错误,不应用scanf("%c", &c),输入的可能是空格或换行符
3.POJ上没有longlong(int前加个longlong好像没啥效果),也就没有"%lld"
  需要64位整数,请用__int64,及"%I64d"

下面是修改过的并查集代码:
//-----------------------------------------
void UFset:: unionset(int root1,int root2)
{
	if(root1 == root2) return;
    if ( parent[root2] < parent[root1] )
    {
        parent[root1] = root2;      
    }
    else 
    {
        parent[root2] = root1;      
    }
}

> #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;
> }

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