NUAA ACM OJ源码

				#include 
				#include 
				
				//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						printf("(%d %d %d)",i,cube[i].dis,cube[i].fa);
					printf("\n");
				}
				void init(int num)
				{
					int i;
					for(i=1;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					{
						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;
				}