I hope you know the beautiful Union-Find structure. In this problem, you’re to implement something similar, but not identical.
The data structure you need to write is also a collection of disjoint sets, supporting 3 operations:
1 p q
Union the sets containing p and q. If p and q are already in the same set, ignore this command.
2 p q
Move p to the set containing q. If p and q are already in the same set, ignore this command
3 p
Return the number of elements and the sum of elements in the set containing p.
Initially, the collection contains n sets: {1}, {2}, {3}, …, {n}.
Input
There are several test cases. Each test case begins with a line containing two integers n and m (1<=n,m<=100,000), the number of integers, and the number of commands. Each of the next m lines contains a command. For every operation, 1<=p,q<=n. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.
Output
For each type-3 command, output 2 integers: the number of elements and the sum of elements.
Sample Input5 71 1 22 3 41 3 53 42 4 13 43 3Output for the Sample Input3 123 7
2 8
题意：给你3种操作，1是将2个集合合并，2是把集合p从原来的集合抽取出来，，放入集合q，如果在一起就忽略本命令，3是查询p所在集合的元素个数，跟该集合的元素之和
思路：科普了一下，目前还没有算法能支持并查集的点直接删除，因为并查集的性质！那么我们可以把抽离出来的点映射到一个新的节点（该节点本身不存在），然后再对原集合进行操作，那么操作其他点的时候就是直接操作每个点的映射了。
特别注意的是操作2，首先要判断两点是否已经在一起了，不然操作就会错！
AC代码：
#include<cstdio>#include<cstring>typedef long long ll;const int maxn=100000+10;int a[maxn];int f[maxn*2],tot[maxn];ll d[maxn];int find(int x){if(x!=f[x]){f[x]=find(f[x]);return f[x];}elsereturn x;}void Union(int u,int v){int x=find(a[u]);int y=find(a[v]);if(x==y)return ;d[y]+=d[x];tot[y]+=tot[x];f[x]=y;}int main(){#ifndef ONLINE_JUDGEfreopen("in.cpp","r",stdin);freopen("out.cpp","w",stdout);#endif // ONLINE_JUDGEint n,m;while(scanf("%d %d",&n,&m)!=EOF){for(int i=0;i<=n;i++){f[i]=i;d[i]=i;a[i]=i;tot[i]=1;}//memset(d,0,sizeof(d));int num=n+1;while(m–){int k;scanf("%d",&k);if(k==1){int u,v;scanf("%d %d",&u,&v);Union(u,v);}else if(k==2){int u,v;scanf("%d %d",&u,&v);if(find(a[u])==find(a[v]))continue;int x=find(a[u]);d[x]-=u;tot[x]–;a[u]=num++;d[a[u]]=u;tot[a[u]]=1;f[a[u]]=a[u];Union(u,v);}else{int q;scanf("%d",&q);int x=find(a[q]);printf("%d %lld\n",tot[x],d[x]);}}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
生活中若没有朋友，就像生活中没有阳光一样
