Almost Union-Find(并查集删除操作)

题意
有n个人，有m个，三种操作
①.合并p所在的集合和q所在的集合
②.将p加入q所在的集合
③.询问p所在的集合中的元素个数以及元素之和

一和三都是普通的并查集操作，主要是二，把一个单独的节点p加入q所在的集合，不太好想。
由于并查集是一个树状结构，内部关系复杂，所以如果将其中的一个点直接拆出来，势必会导致树状结构解体
用一个id[i]数组表示元素i的编号，每次的删除操作即给元素i分配一个新的编号。因为要求输出集合的元素个数和他们的和，所以我们需要维护这个信息，因为并查集的根结点在路径压缩中是不变的，所以将这两个信息维护在根结点上就行了

#include <string.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=2e5+10;
int id[maxn],pre[maxn];
int sum[maxn],num[maxn];
int n,m,cnt;
int find(int u)
{
	if (pre[u]==u)
		return u;
	else
	{
		pre[u]=find(pre[u]);
		return pre[u];
	}
}
void merge(int u,int v)
{
	int t1=find(id[u]),t2=find(id[v]);
	if (t1==t2)
		return ;
	pre[t1]=t2;
	num[t2]+=num[t1];
	sum[t2]+=sum[t1];
}
int main()
{
	int i,j,n,m,u,v,c;
	while(~scanf("%d%d",&n,&m))
	{
		int t1,t2;
		cnt=n;
		for (i=1; i<=n; i++)
		{
			id[i]=pre[i]=sum[i]=i;
			num[i]=1;
		}
		for (i=1; i<=m; i++)
		{
			scanf("%d",&c);
			if (c==1)
			{
				scanf("%d%d",&u,&v);
				merge(u,v);
			}
			else if(c==2)
			{
				scanf("%d%d",&u,&v);
				int t1=find(id[u]),t2=find(id[v]);
				if (t1!=t2)
				{
					num[t1]--;
					sum[t1]-=u;//删除此节点
					id[u]=++cnt;//u重新申请新节点
					pre[id[u]]=id[u];
					num[id[u]]=1;
					sum[id[u]]=u;
					merge(u,v);//u,id[u]代表的新节点初始化
				}
			}
			else if (c==3)
			{
				scanf("%d",&u);
				u=find(id[u]);
				printf("%d %d\n",num[u],sum[u]);
			}
		}
	}
	return 0;
}
/*
并查集删除操作
三种操作：
1.合并p所在的集合和q所在的集合
做法：p和q进行简单的并查集根节点合并即可，
如果p，q两个的根节点一样，直接continue；

2.将p节点加入q所在的集合
2.1 在并查集中删除一个节点是很麻烦的事情，所以我们引入一个新的东西，
用 id[i] 代替原有的 i 进行并查集操作，
如果有一个点我们想把它从某一个集合中拿出来，
就重新给 i 定义一个新的 id[i]=++cnt,这样就i不变，id变化。

2.2 用一个数组id[]表示p所代表的代号，p当前的根为：
pre[id[p]]
当p被2操作时，我们只要改变它的id[p]（比如 id[p]=++n），
我们就可以让p有一个新的pre[]表示，而不用改变原来的根的表示，
所以当后面的操作又用到p时，现在的 pre[id[p]] 已经不是之前那个了。

3.询问p所在集合中的元素个数以及元素之和
做法：开一个size数组和sum数组，在合并f数组时一起合并.

*/

Almost Union-Find(并查集删除操作)

原文：https://www.cnblogs.com/shidianshixuan/p/14351799.html