题解 | #叠积木(带权并查集，记录到根节点举例和本列积木数量）#
叠积木
https://ac.nowcoder.com/acm/problem/235622
这道题维护的附加信息是某一块积木下面还有多少块积木，并查集来写用两个数组 d[ ] 和 cnt [ ], d [ ]表示这块积木到上一个节点有多少块积木
比如 x的祖宗节点是 p[x],那d[x]代表的就是x到最下面一块积木也就是祖宗节点p[x]的数量 d[ i ]：i 距离根节点（队头）的距离
合并的时候只需要加上下面一列积木就是自己下面的积木数量
cnt[ i ]：i 所在的连通块有多少个元素（ i 所在那一列的积木数目 ）
但d[ ] 数组的一个维护就要依靠cnt数组来解决，cnt记录某一列有多少积木，当然cnt [ 祖宗节点 ]才有效
所以在连接两列积木时，只需要上面一列的祖宗节点也就是最下面那块积木 x 指向下面一列积木的祖宗节点 y ，那上面一列祖宗节点 x 到他的祖宗节点 y 的积木数量d [ x ] = cnt [ y ]
那这两列结合之后的积木数量就一个数 cnt [ y ] += cnt [ x ];
图中size代表的是cnt
会了的话可以试试这题
// 总所周知如果x！=p[x],那么只需要找p[x]的祖宗节点就是x的祖宗节点，只会找一次，这个不好解释，可以自己模拟一下
#include<bits/stdc++.h>
using namespace std;
const int N = 300010;
int n;
int fa[N];
int d[N];
int cnt[N];
int find2(int x) {
if (fa[x] != x) {
int t = find2(fa[x]);//向上递推找祖父
d[x] += d[fa[x]];//向下堆叠积木数量
fa[x] = t;
}
return fa[x];
}
void unite(int x, int y) {//将x叠到y所在的积木列的上面
int f1 = find2(x);
int f2 = find2(y);
if (f1 != f2) {//祖父不相同，要继续堆叠积木数量
fa[f1] = f2;
d[f1] = cnt[f2]; //cnt代表f2所在积木列的数量
cnt[f2] += cnt[f1]; //结合之后祖宗节点是f2 ，这一列的数量就等于之前两列数量之和
}
}
int main() {
cin >> n;
for (int i = 1; i < N; i++)
{
fa[i] = i;
d[i] = 0;
cnt[i] = 1;
} //初始化，d[]是本身下面的积木数量，初始为0，cnt是这一列的积木数量，初始时每一列都为1
for (int i = 1; i <= n; i++) {
char c;
cin >> c;
if (c == 'M') {
int x, y;
cin >> x >> y;
unite(x, y); //堆叠操作
}
else {
int x;
cin >> x;
find2(x);//计算d[x]的数量
cout << d[x] << endl;
}
}
return 0;
}
同程旅行工作强度 17人发布