uva 11987 Almost Union-Find (并查集)

题目：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18692

题意：设计一个并查集,支持三种操作①将两个集合合并②将一个集合的一个元素移到另外一个集合③查询集合元素个数和元素之和

分析：由于操作②可能导致将整个集合移走（移走根节点）,那么初始化的时候,以id+N为根节点就好了。

代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 2e6;
const int OVER = 1e6; 
int Sum[maxn],Size[maxn],Fa[maxn],N,Q;
int Find(int x)
{
	if(Fa[x]==x)
		return x;
	int root=Find(Fa[x]);
	return Fa[x]=root;
}

int main()
{
	int i,j,tp,x,y;
	while(scanf("%d%d",&N,&Q)!=EOF)
	{
		for(i=0;i<=N;i++)
			Fa[i]=i+OVER;
		for(i=OVER;i<=OVER+N;i++)
		{
			Fa[i]=i;
			Sum[i]=i-OVER;
			Size[i]=1;
		}
		while(Q--)
		{
			scanf("%d",&tp);
			if(tp==1)
			{
				scanf("%d%d",&x,&y);
				int root1=Find(x),root2=Find(y);
				if(root1==root2)
					continue ;
				Fa[root1]=root2;
				Sum[root2]+=Sum[root1];
				Size[root2]+=Size[root1];
			}
			else if(tp==2)
			{
				scanf("%d%d",&x,&y);
				int root1=Find(x),root2=Find(y);
				if(root1==root2)
					continue ;
				Size[root1]--;
				Size[root2]++;
				Sum[root1]-=x;
				Sum[root2]+=x;
				Fa[x]=root2;
			}
			else
			{
				scanf("%d",&x);
				int root=Find(x);
				printf("%d %d\n",Size[root],Sum[root]);
			}
		}
	}
	return 0;
}

uva 11987 Almost Union-Find (并查集)

原文：http://blog.csdn.net/w20810/article/details/47312063