并查集学习心得
int find(int x)//并查集找父亲
{if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];
}
void add(int x,int y)//合并
{int fx=find(x);int fy=find(y);if(x!=y) fa[fx]=fy;
}
P1197 [JSOI2008] 星球大战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
洛谷p1197星球大战 :并查集+逆向思考_phrame_的博客-CSDN博客
这题由于并查集不好进行删除点的操作,所以反向操作,把删除点反向成一个个添加新的点,注意判断连通块的方法是看,fa[i]==i,那么是一个连通块,父亲相等为一个连通块
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
vector<int>ans;
vector<int> a[N];//存图
int fa[N];
int h[N];//存要摧毁的
int vis[N];//标记是否要摧毁
int find(int x)//并查集
{if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];
}
void add(int x,int y)//合并
{int fx=find(x);int fy=find(y);if(x!=y) fa[fx]=fy;
}
signed main()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++){fa[i]=i;//初始化 }for(int i=1;i<=m;i++){int u,v;cin>>u>>v;a[u].push_back(v);a[v].push_back(u);//双向存图 }int k;cin>>k;for(int i=1;i<=k;i++){cin>>h[i];vis[h[i]]=1;//标记要摧毁的 }for(int i=0;i<n;i++){for(auto x:a[i])//遍历a[i]所有的点 {if(vis[x] ||vis[i])//去掉要摧毁的 {continue;}add(x,i);//对不摧毁的点合并处理 }}int cnt=0;for(int i=0;i<n;i++){if(!vis[i]&&fa[i]==i){cnt++;//没有修复前连通块的个数 }} ans.push_back(cnt);//最后一种全摧毁完的答案//开始修复,倒推for(int i=k;i>=1;i--){int x=h[i];cnt++;//把它当成独立的连通块 vis[x]=0;//被修复 for(auto u:a[x]){if(!vis[u]&&find(x)!=find(u)){add(u,x); cnt--;//减去不是连通块的 }}ans.push_back(cnt);} reverse(ans.begin(),ans.end());for(auto c:ans) {cout<<c<<endl;}return 0;
}
相关文章:
并查集学习心得
int find(int x)//并查集找父亲 {if(x!fa[x]) fa[x]find(fa[x]);return fa[x]; } void add(int x,int y)//合并 {int fxfind(x);int fyfind(y);if(x!y) fa[fx]fy; } P1197 [JSOI2008] 星球大战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 洛谷p1197星球大战 :并查集逆向…...
自动驾驶之—LaneAF学习相关总结
0.前言: 最近在学习自动驾驶方向的东西,简单整理一些学习笔记,学习过程中发现宝藏up 手写AI 1. 概述 Laneaf思想是把后处理放在模型里面。重点在于理解vaf, haf,就是横向聚类:中心点,纵向聚类&…...
软考系统架构之案例篇(Redis相关概念)
案例篇-Redis相关概念 1. Redis与Memcache能力对比2. Redis集群切片的常见方式3. Redis分布式存储方案4. Redis数据分片方案5. Redis持久化 1. Redis与Memcache能力对比 工作MemCacheRedis数据类型简单 key/value 结构丰富的数据结构持久性不支持支持分布式存储客户端哈希分片…...
黑客入门指南,学习黑客必须掌握的技术
黑客一词,原指热心于计算机技术,水平高超的电脑专家,尤其是程序设计人员。是一个喜欢用智力通过创造性方法来挑战脑力极限的人,特别是他们所感兴趣的领域,例如电脑编程等等。 提起黑客,总是那么神秘莫测。在…...
定档11月2日,YashanDB 2023年度发布会完整议程公布
数据库作为支撑核心业务的关键技术,对数字经济的发展有着重要的支撑作用,随着云计算、AI等技术的迅猛发展和数据量的爆发式增长,推动着数据库技术的加速创新。 为了应对用户日益复杂的数据管理需求,赋能行业国产化建设和数字化转型…...
composer安装thinkphp6报错
composer安装thinkphp6报错, 查看是否安装了对应的PHP扩展,我这边使用的是宝塔的环境,全程可以可视化操作 这样就可以安装完成了...
此页面不能正确地重定向
这种是由于条件判断有误,程序不断的重定向到一个页面,而造成的死循环的情况 下面列举一个常出现的场景之一 1、使用过滤器实现登录验证错误处理 解释:当用户访问login.jsp进行登录的时候,这个时候请求会被Filter捕获࿰…...
【Apache Flink】实现有状态函数
文章目录 在RuntimeContext 中声明键值分区状态通过ListCheckPonitend 接口实现算子列表状态使用CheckpointedFunction接口接收检查点完成通知参考文档 在RuntimeContext 中声明键值分区状态 Flink为键值分区状态(Keyed State)提供了几种不同的原语&…...
Android原生项目集成uniMPSDK(Uniapp)遇到的报错总结
uni小程s序SDK 集成到Android原生项目:老项目中用到的库较多,会出现几种冲突问题,总结如下: 报错1: Execution failed for task :app:processDebugManifest. > Manifest merger failed with multiple errors, see logs Andro…...
Linux redis 安装
1、解压 tar -zxvf redis-5.0.10.tar.gz 2、cd /data/redis-5.0.10 文件夹 3、make 等待make命令执行完成即可。 make命令报错:cc 未找到命令,系统中缺少gcc,执行命令安装 gcc: yum -y install gcc automake autocon…...
在Win11上部署ChatGLM3详细步骤
023年10月27日,智谱AI于2023中国计算机大会(CNCC)上,推出了全自研的第三代基座大模型ChatGLM3及相关系列产品,这也是智谱AI继推出千亿基座的对话模型ChatGLM和ChatGLM2之后的又一次重大突破。此次推出的ChatGLM3采用了…...
系列七、动态代理
一、概述 二、Jdk动态代理案例 2.1、Star /*** Author : 一叶浮萍归大海* Date: 2023/10/27 17:16* Description:*/ public interface Star {/*** 唱歌* param name 歌曲名字* return*/String sing(String name);/*** 跳舞*/void dance(); } 2.2、BigStar /*** Author : 一叶…...
Kafka集群搭建与SpringBoot项目集成
本篇文章的目的是帮助Kafka初学者快速搭建一个Kafka集群,以及怎么在SpringBoot项目中使用Kafka。 kafka集群环境包地址:百度网盘 请输入提取码 提取码:x9yn 一、Kafka集群搭建 1、准备环境 (1)准备三台…...
一个简单的注册的页面,如有错误请指正;(3.JavaScript)
这段代码是一个JavaScript函数,实现了用户登录和上传图片的功能,并包含了一些辅助函数。让我一一解释: 1. login():这个函数用于登录操作。首先,通过$(#name).val()来获取ID为name的元素的值,同理获取其他…...
selenium (自动化概念 测试环境配置)
什么是自动化测试 自动化测试介绍 自动化测试指软件测试的自动化,在预设状态下运行应用程序或者系统. 预设条件包括正常和异常,最后评估运行结果。 自动化测试,就是将人为驱动的测试行为转化为机器执行的过程。 【机器 代替 人工】 自动化…...
Mybatis-Plus(企业实际开发应用)
一、Mybatis-Plus简介 MyBatis-Plus是MyBatis框架的一个增强工具,可以简化持久层代码开发MyBatis-Plus(简称 MP)是一个 MyBatis 的增强工具,在 MyBatis 的基础上只做增强不做改变,为简化开发、提高效率而生。 官网&a…...
Spring Web MVC入门
一:了解Spring Web MVC (1)关于Java开发 🌟Java开发大多数场景是业务开发 比如说京东的业务就是电商卖货、今日头条的业务就推送新闻;快手的业务就是短视频推荐 (2)Spring Web MVC的简单理解 💗Spring Web MVC:如何使…...
【C++】mapset的底层结构 -- AVL树(高度平衡二叉搜索树)
前面我们对 map / multimap / set / multiset 进行了简单的介绍,可以发现,这几个容器有个共同点是:其底层都是按照二叉搜索树来实现的。 但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索…...
吴恩达《机器学习》1-4:无监督学习
一、无监督学习 无监督学习就像你拿到一堆未分类的东西,没有标签告诉你它们是什么,然后你的任务是自己找出它们之间的关系或者分成不同的组,而不依赖于任何人给你关于这些东西的指导。 以聚类为例,无监督学习算法可以将数据点分成…...
一个简单的注册页面,如有错误请指正(2.css)
这段CSS代码定义了页面的样式,让我逐个解释其功能: 1. * {}:通配符选择器,用于将页面中的所有元素设置统一的样式。这里将margins和paddings设置为0,以去除默认的边距。 2. div img {}:选择页面中所有div…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
