#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define N 6000001
int v[N],d[N],n;
int findd(int p)
{
	int i;
	for(i=p;i!=v[i];i=v[i])
		v[i]=v[v[i]];
	return i;
}
void linkp(int pa,int pb)
{
	pa=findd(pa);
	pb=findd(pb);
	if(pa==pb) return;
	if(d[pa]>d[pb]) 
	{
		v[pb]=pa;
		d[pa]+=d[pb];
	}
	else 
	{
		v[pa]=pb;
		d[pb]+=d[pa];
	}
}
int suma,sumb;
bool judge(int pa,int pb)
{
	pa=findd(pa);
	pb=findd(pb);
	if(pa==pb) {
		suma++;
		return 1;
	}
	sumb++;
	return 0;
}
void init()
{
	int i;
	for(i=1;i<=n;i++)
	{
		v[i]=i;
		d[i]=1;
	}
}
int main()
{
	//freopen("a.in","r",stdin);
	char s[300],g[10];
	int r[5],k=0,i;

	while(gets(s))
	{
		 k=0;
		 i=1;
		 while(sscanf(s+i,"%s",g)!=EOF)
		 {
			 do ++i;
			 while(s[i]==' ');
			 i+=strlen(g);
			 r[k]=atoi(g);
//			 printf("%d ",r[k]);
			 k++;
		 }
//		 printf("\n");
		 if(s[0]=='c' || s[0]=='C')
		 {
			 if(k==2) linkp(r[0],r[1]);
			 else if(k==3)
			 {
				 for(i=0;i<r[2];i++)
					 linkp(r[0],r[1]+i);
			 }
			 else if(k==4)
			 {
				 if(r[3]==0) linkp(r[0],r[1]);
				 else 
				 for(i=0;i<r[2];i++)
				 {
					 linkp(r[0],r[1]);
					 r[1]+=r[3];
				 }
			 }
			 else 
			 {
				 if(r[3]==0 && r[4]==0) linkp(r[0],r[1]);
				 else 
				 for(i=0;i<r[2];i++)
				 {
					 linkp(r[0],r[1]);
					 r[0]+=r[4];
					 r[1]+=r[3];
				 }
			 }
		 }
		 else if(s[0]=='q' || s[0]=='Q')
		 {
			 suma=sumb=0;
			 if(k==2) judge(r[0],r[1]);
			 else if(k==3)
			 {
				 for(i=0;i<r[2];i++)
					 judge(r[0],r[1]+i);
			 }
			 else if(k==4)
			 {
				 if(r[3]==0) judge(r[0],r[1]);
				 else 
				 for(i=0;i<r[2];i++)
				 {
					 judge(r[0],r[1]);
					 r[1]+=r[3];
				 }
			 }
			 else 
			 {
				 if(r[3]==0 && r[4]==0) judge(r[0],r[1]);
				 else 
				 for(i=0;i<r[2];i++)
				 {
					 judge(r[0],r[1]);
					 r[0]+=r[4];
					 r[1]+=r[3];
				 }
			 }
			 printf("%d - %d\n",suma,sumb);
		 }
		 else 
		 {
			 n=r[0];
			 init();
		 }
	}
	return 0;
}

• Re:用并查集做的 Why wrong?期待高手指点 (2359) newton88518 2006-11-13 16:11:27