带权并查集--删除--UVA11987

题意：     n个数字 m个操作     1：  x  y 合并 x,y     2： 将x元素移动到y元素所在的集合     3:  输出x集合中元素个数，和总和 思路：     删除并查集： 并非把根节点或者子节点直接删除，而是保留。                  之后将删除的元素放到数组最后进行新一轮操作。                  而原值所在的集合的权在删除时进行更新就好     删除并查集实现：既然要更新元素到当前数组最后，就要记录下id[x]，下次才能直接进行 #include <iostream> #include <stdio.h> using namespace std; int id[200010]; int father[200010]; int num[200010]; int sum[200010]; int cot; int n,m; void init(int n) { for(int i=1; i<=n; i++) { father[i]=i; sum[i]=i; num[i]=1; id[i]=i; } } int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } void Del(int x) { int tmp=find(id[x]); sum[tmp]-=x; num[tmp]--; cot++; father[cot]=cot; num[cot]=1; sum[cot]=x; id[x]=cot; } void Union(int x,int y) { int root1=find(x); int root2=find(y); if(root1!=root2) { num[root1]+=num[root2]; father[root2]=root1; sum[root1]+=sum[root2]; } } int main() { while(~scanf("%d%d",&n,&m)) { init(n); cot=n; while(m--) { int op,x,y; scanf("%d",&op); if(op==1) { scanf("%d%d",&x,&y); Union(id[x],id[y]); } else if(op==2) { scanf("%d%d",&x,&y); if(find(id[x])!=find(id[y])) { Del(x); Union(id[x],id[y]); } } else { scanf("%d",&x); int tmp=find(id[x]); printf("%d %d\n",num[tmp],sum[tmp]); } } } return 0; }