这道题维护的附加信息是某一块积木下面还有多少块积木，并查集来写用两个数组 d[ ] 和 cnt [ ], d [ ]表示这块积木到上一个节点有多少块积木
比如 x的祖宗节点是 p[x],那d[x]代表的就是x到最下面一块积木也就是祖宗节点p[x]的数量 &nb
展开全文
一、把每堆积木看作一个集合，最下方的积木是集合的根节点
二、只需要维护集合中每个元素到根节点的距离d[x](这题和食物链那题基本相同）
三、还需要维护每个集合中元素的数量s[x]，目的是为了方便后面维护d[x]
四、find(x)函数返回x的祖宗节点，同时更新从x节点到祖宗节点路径上所有的节点d[x
展开全文
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#
展开全文
一个需要维护附加信息的并查集。需要维护的信息为某编号为 x 的积木下方有多少块积木。直接维护需要更新一棵树的所有节点，这显然是不方便的。
在这里我们选择让根节点保存某个编号下的箱子总数，然后下面被连接的根节点保存其下方有多少箱子。这样查询某个编号的箱子下面的箱子个数只需要向
展开全文
">using namespace std;
const int N = 30010;
int d[N];//代表当前节点到其祖宗节点的长度
int c[N];//当c[n](n==祖宗节点)c[n]表示当前列的大小
int fa[N];//用于并查集记录父亲节点
int find(int a)
{
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
