【UVA11987】Almost Union-Find

题目就告诉我们要用并查集了，操作1和3用裸的带权并查集就行了，

操作2相当于将p结点从当前树中删除，再插入到q的树中，直接删除的话比较麻烦，不妨把它的“尸体”留在原来的地方，在q的树中插入一个新的点，维护一个指向编号为p点的指针即可

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int MAXN=2000010;

int n,q,fa[MAXN],size[MAXN],sum[MAXN],m[MAXN],cnt;

inline int read(){

	int x=0; char c=getchar();

	while(c<'0') c=getchar();

	while(c>='0') x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x;

}

inline int find(int x){

	if(fa[x]==x) return x;

	return fa[x]=find(fa[x]);

}

int main()

{

	while(scanf("%d%d",&n,&q)!=EOF){

		cnt=n;

		for(int i=1;i<=n;++i)

			fa[i]=i,size[i]=1,sum[i]=i,m[i]=i;

		int op,x,y;

		while(q--){

			op=read();

			if(op==1){

				x=read(),y=read();

				x=m[x]; y=m[y];

				if(find(x)==find(y)) continue;

				if(rand()%2) swap(x,y);

				size[find(y)]+=size[find(x)];

				sum[find(y)]+=sum[find(x)];

				fa[find(x)]=find(y);

			}

			else if(op==2){

				int p=read(),q=read();

				x=m[p]; y=m[q];

				if(find(x)==find(y)) continue;

				--size[find(x)];

				++size[find(y)];

				sum[find(x)]-=p;

				sum[find(y)]+=p;

				m[p]=++cnt;

				fa[cnt]=find(y);

			}

			else{

				x=read(); x=m[x];

				printf("%d %d\n",size[find(x)],sum[find(x)]);

			}

		}

	}

	return 0;

}

巴特西

【UVA11987】Almost Union-Find

最新文章

热门文章