并查集学习心得
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…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
[特殊字符] 手撸 Redis 互斥锁那些坑
📖 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作,想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁,也顺便跟 Redisson 的 RLock 机制对比了下,记录一波,别踩我踩过…...
EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势
一、WebRTC与智能硬件整合趋势 随着物联网和实时通信需求的爆发式增长,WebRTC作为开源实时通信技术,为浏览器与移动应用提供免插件的音视频通信能力,在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能,对实时…...
