[并查集] UVA11987 Almost Union-Find

问题描述

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

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

输入格式

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

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

输出格式

输出行数为 $3$ 号命令的总数。
每一行输出两个整数 $a$ 和 $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\le n,m\le 10^5,1\le p,q\le n$ 。

题解

使用并查集进行维护，$1$ 和 $3$ 操作都是普通的并查集操作，$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, uint 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;
}