博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
并查集(删除) UVA 11987 Almost Union-Find
阅读量:6479 次
发布时间:2019-06-23

本文共 403 字,大约阅读时间需要 1 分钟。

 

题意:训练指南P246

分析:主要是第二种操作难办,并查集如何支持删除操作?很巧妙的方法:将并查集树上p的影响消除,即在祖先上(sz--, sum -= p),然后为p换上马甲:id[p] = ++pos(可多次),这样id[p]就相当于是新的一个点,那么在Find(x)寻找祖先时要用x的马甲来寻找,即Find (id[x])。

#include 
using namespace std;const int N = 2e5 + 5;int rt[N], sz[N], sum[N], id[N/2];int n, m;void init() { memset (rt, -1, sizeof (rt)); for (int i=1; i

  

转载于:https://www.cnblogs.com/Running-Time/p/5130608.html

你可能感兴趣的文章
git bash 风格调整
查看>>
linux操作系统加固软件,系统安全:教你Linux操作系统的安全加固
查看>>
linux中yum源安装dhcp,24.Linux系统下动态网络源部署方法(dhcpd)
查看>>
HDOJ-1010 Tempter of the Bone
查看>>
JavaNIO基础02-缓存区基础
查看>>
日本开设无人机专业,打造无人机“人才市场”
查看>>
190行代码实现mvvm模式
查看>>
兼容几乎所有浏览器的透明背景效果
查看>>
jeesite 框架搭建与配置
查看>>
Linux VNC server的安装及简单配置使用
查看>>
阿里宣布开源Weex ,亿级应用匠心打造跨平台移动开发工具
查看>>
Android项目——实现时间线程源码
查看>>
招商银行信用卡重要通知:消费提醒服务调整,300元以下消费不再逐笔发送短信...
查看>>
C#_delegate - 调用列表
查看>>
[转]Windows的批处理脚本
查看>>
多维数组元素的地址
查看>>
数据库运维体系_SZMSD
查看>>
js的AJAX请求有关知识总结
查看>>
Eclipse添加新server时无法选择Tomcat7的问题
查看>>
三分 POJ 2420 A Star not a Tree?
查看>>