POJ-1988-Cube Stacking
题目链接
题目大意：给定编号为1到30000的小块。可以进行合并和查询两种操作
- 合并：将含有x的整块摞到含有y的整块上面，合并成一个新的整块
- 查询：输出x下方的块的数量
一眼并查集，但就是不知道怎么写。想了很久才想到要以每个整块的底块作为并查集的根，并维护某个块底下的小块的数量作为并查集的权值。另开一个并查集，以每个整块的顶块作为根。
每次合并，都将x所在整块的底块的权值赋值为y所在整块的小块总数。不难知道，y所在的整块的小块总数就是y的顶块下面的小块的数量，即带权并查集中y顶块的权值+1。
在带权并查集的查找合并二合一（ffind）的过程中，对于每一个点，如果它的f不为本身，就把它的权值累加上它此时的f的权值。写的时候我对带权并查集并不算非常熟悉，觉得这么写会导致重复查询某一点时重复累加，但其实不会。因为根的权值永远是0。一个点累加过一次之后，这个点就会指向根节点，所以重复累加也是加的0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
int f[30006], sum[30006], fd[30006];
int ffind(int x)
{
if (x == f[x])
return f[x];
int t = f[x];
f[x] = ffind(t);
sum[x] += sum[t];
return f[x];
}
int dfind(int x)
{
if (x == fd[x])
return x;
return fd[x] = dfind(fd[x]);
}
void mge(int x, int y)
{
x = ffind(x);
y = ffind(y);
if (x == y)
return;
f[x] = y;
y = dfind(y);
ffind(y);
sum[x] = sum[y] + 1;
fd[y] = x;
}
int main()
{
char op[5];
int a, b, _, i;
for (i = 0; i <= 30000; i++)
f[i] = fd[i] = i;
scanf("%d", &_);
while (_--)
{
scanf("%s%d", op, &a);
if (op[0] == 'C')
{
ffind(a);
printf("%d\n", sum[a]);
continue;
}
scanf("%d", &b);
mge(a, b);
}
return 0;
}
|