[并查集] UVA11987 Almost Union-Find

问题描述

有 n n n 个集合， m m m 次操作。规定第 i i i 个集合里初始只有 i i i 。
有三种操作：

1. 输入两个元素 p p p 和 q q q ，若 p p p 和 q q q 不在一个集合中，合并两个元素的集合。
2. 输入两个元素 p p p 和 q q q ，若 p p p 和 q q q 不在一个集合中，把 p p p 添加到 q q q 所在的集合。
3. 输入一个元素 p p p ，查询 p p p 所在集合的元素个数和所有元素之和。

输入格式

本题有多组数据。
对于每组数据：

第一行输入 n n n 和 m m m 两个整数。
接下来 m m m 行，每行第一个数 k k k 代表选择哪一个命令，若 k k k 是 1 1 1 或 2 2 2 命令，则再输入两个整数 p p p 和 q q q 。若 k k k 是 3 3 3，则输入一个整数 p p p 。

输出格式

输出行数为 3 3 3 号命令的总数。
每一行输出两个整数 a a a 和 b b b，即元素个数和元素和。

样例

样例输入1：

5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3

样例输出1：

3 12
3 7
2 8
3 12
3 7
2 8

数据范围

对于所有数据， 1 ≤ n , m ≤ 1 0 5 , 1 ≤ p , q ≤ n 1 \le n, m \le 10^5, 1\le p, q \le n 1≤n,m≤105,1≤p,q≤n 。

题解

使用并查集进行维护， 1 1 1 和 3 3 3 操作都是普通的并查集操作， 2 2 2 操作需要维护删除操作。

删除：对于每个点，将代表记为虚拟的点，并记录每个点对应虚拟点的位置。这样删除就可以直接从以前的并查集中操作，再进行创建新的点了。

int u[200010];
int siz[200010], sum[200010];//大小，和
int bh[200010];//每个点对应现有的编号
int get_father(int x){//查找（路径压缩）
	……
}
int main(){
	while(scanf("%d %d", &n, &m) != EOF){
		清空 siz, summ, u
		int cnt = n;
		//初始化
		for(int i = 1; i <= n; ++ i){
			u[i] = i;
			siz[i] = 1;
			sum[i] = i;
			bh[i] = i;
		}
		for(int i = 1; i <= m; ++ i){
			int x, y, z;
			scanf("%d", &x);
			if(x == 1){//普通的合并
				scanf("%d %d", &y, &z);
				int t1 = get_father(bh[y]), t2 = get_father(bh[z]);
				if(t1 == t2){
					continue;
				}
				u[t1] = t2;
				siz[t2] += siz[t1];
				sum[t2] += sum[t1];
			}
			else if(x == 2){
				scanf("%d %d", &y, &z);
				int t1 = get_father(bh[y]), t2 = get_father(bh[z]);
				if(t1 == t2){
					continue;
				}
				//从前一个集合删除
				siz[t1] --;
				sum[t1] -= y;
				//新建虚拟点，并指向 t2
				++ cnt；
				u[cnt] = t2;
				siz[cnt] = 1;
				sum[cnt] = y;
				siz[t2] ++;
				sum[t2] += y;
				bh[y] = cnt;//记录对应集合
			}
			else{
				scanf("%d", &y);
				printf("%d %d\n", siz[get_father(bh[y])], sum[get_father(bh[y])]);
			}
		}
	}
	return 0;
}