首页 > 代码库 > UVa 11987 Almost Union-Find(支持删除操作的并查集)
UVa 11987 Almost Union-Find(支持删除操作的并查集)
传送门
Description
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).
Output
For each type-3 command, output 2 integers: the number of elements and the sum of elements.
Explanation
Initially: {1}, {2}, {3}, {4}, {5}
Collection after operation 1 1 2: {1,2}, {3}, {4}, {5}
Collection after operation 2 3 4: {1,2}, {3,4}, {5} (we omit the empty set that is produced when taking out 3 from {3})
Collection after operation 1 3 5: {1,2}, {3,4,5}
Collection after operation 2 4 1: {1,2,4}, {3,5}
Sample Input
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
Sample Output
3 12
3 7
2 8
思路
题意:
给出1-N的数,一开始每个数自形成一个集合,要求支持一下操作
- 将元素 p 所在集合与元素 q 所在集合合并
- 将元素 p 移到元素 q 所在集合
- 询问元素 p 所在集合有多少个元素,和为多少
题解:
第一和第三个操作都是很裸的并查集,关键在于操作2,很容易可以想到,元素 p 移到元素 q所在集合,可以先在元素 p 所在集合将其删除,然后把元素 p 与元素 q 所在集合合并。而这一步的关键在于删除操作,如果 p 是叶子节点,直接改变 p 的父亲指向就行,但是 p 即所在集合的根节点又当如何,将其删除的话其子节点需要重新建立关系,这个过程还是有一定复杂性的。我们可以采取另外的思路:二次哈希法(ReHash),对于每个结点都有一个哈希值,在进行查找之前需要将x转化成它的哈希值HASH[x],那么在进行删除的时候,只要将x的哈希值进行改变,变成一个从来没有出现过的值(可以采用一个计数器来实现这一步),然后对新的值建立集合,因为只有它一个元素,所以必定是一个新的集合。这样做可以保证每次删除操作的时间复杂度都是O(1)的,而且不会破坏原有树结构,唯一的一个缺点就是每删除一个结点其实是多申请了一块内存,如果删除操作无限制,那么内存会无限增长。
简单的说,就是建立虚拟节点,这样原来的节点还在树当中,并不会破坏其结构,开辟一个id[ ]数组表示元素 x 对应的值。
#include<bits/stdc++.h>using namespace std;const int maxn = 100005;int cnt,fa[maxn],num[maxn],sum[maxn],id[maxn];void init(int N){ for (int i = 0;i <= N;i++) { fa[i] = id[i] = sum[i] = i; num[i] = 1; } cnt = N;}int find(int x){ int r = x; while (r != fa[r]) r = fa[r]; int i = x,j; while (i != r) { j = fa[i]; fa[i] = r; i = j; } return r;}void Union(int x,int y){ int fx = find(id[x]),fy = find(id[y]); fa[fx] = fy; num[fy] += num[fx]; sum[fy] += sum[fx];}void Delete(int x){ int fx = find(id[x]); --num[fx]; sum[fx] -= x; id[x] = ++cnt,fa[id[x]] = id[x],num[id[x]] = 1,sum[id[x]] = x;}int main(){ int N,M; while (~scanf("%d%d",&N,&M)) { int opt,x,y; init(N); while (M--) { scanf("%d",&opt); if (opt == 1) { scanf("%d%d",&x,&y); if (find(id[x]) != find(id[y])) Union(x,y); } else if (opt == 2) { scanf("%d%d",&x,&y); if (find(id[x]) != find(id[y])) Delete(x),Union(x,y); } else { scanf("%d",&x); printf("%d %d\n",num[find(id[x])],sum[find(id[x])]); } } } return 0;}
UVa 11987 Almost Union-Find(支持删除操作的并查集)