poj 1988 并查集.txt

ACM资料大集合

#include <stdlib.h>
#include <stdio.h>

//POJ 1988 并查集
//疑问：所有集合的树的层数（初始都为2）最多不超过4？
#define NMAX 30005
typedef struct point
{
	int fa;//父亲节点
	int dis;//在集合里，该方块的上面有几个方块
	int sum;//这个集合有几个方块
}point;

point cube[NMAX];

void print()
{
	int i;
	for(i=1;i<=10;i++)
		printf("(%d %d %d)",i,cube[i].dis,cube[i].fa);
	printf("\n");
}
void init(int num)
{
	int i;
	for(i=1;i<=num;i++)
	{
		cube[i].fa=cube[i].dis=0;//根节点dis为0
		cube[i].sum=1;
	}
}

int getdis(int root,int a)
{
	if(cube[a].fa!=0)
	{
		cube[a].dis+=getdis(root,cube[a].fa);
		cube[a].fa=root;//压缩路径
	}
	return cube[a].dis;
}
int find_2(int a)
{	//递归方式实现
	int root;
	if(cube[a].fa!=0)
	{
		root=find_2(cube[a].fa);
		cube[a].dis=getdis(root,a);
	}
	if(cube[a].fa!=0) return cube[a].fa;
	else return a;
}
int find_1(int a)
{	//非递归方式实现
	int s=0,st=a,tt,root;
	while(cube[st].fa!=0)
	{
		s+=cube[st].dis;
		st=cube[st].fa;
	}
	root=st;
	st=a;	
	while(cube[st].fa!=0)
	{
		tt=cube[st].dis;
		cube[st].dis=s;
		s-=tt;
		tt=cube[st].fa;
		cube[st].fa=root;//压缩路径
		st=tt;
	}
	return st;
}

void move_2(int x,int y)
{
	x=find_2(x);
	y=find_2(y);
	cube[y].fa=x;
	cube[y].dis=cube[x].sum;
	cube[x].sum+=cube[y].sum;
}

void move_1(int x,int y)
{
	x=find_1(x);
	y=find_1(y);
	cube[y].fa=x;
	cube[y].dis=cube[x].sum;
	cube[x].sum+=cube[y].sum;
}

int main()
{
	int i,num,a,b;
	char action[3];
	scanf("%d",&num);
	init(NMAX);
	for(i=1;i<=num;i++)
	{
		scanf("%s",&action);
		if(action[0]=='M')
		{
			scanf("%d %d",&a,&b);
			move_2(a,b);
		}
		else if(action[0]=='C')
		{
			scanf("%d",&a);
			printf("%d\n",cube[find_2(a)].sum-cube[a].dis-1);
		}
//		print();
//		printf("%d %d\n",i,num);
	}
//	system("pause");
	return 0;
}