并查集进阶版


过关代码如下
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;int n, m;
vector<int> edg[400005];
int a[400005], be[400005]; // a的作用就是存放要摧毁
int k;
int fa[400005];
int daan[400005];void add(int x, int y) {edg[x].push_back(y);edg[y].push_back(x);
}int find(int x) {if (x == fa[x]) return x;return fa[x] = find(fa[x]);
}void uni(int x, int y) {int xx = find(x), yy = find(y);if (xx == yy) return;fa[xx] = yy;
}int main() {cin >> n >> m;int l, r;for (int i = 1; i <= m; i++) {cin >> l >> r;add(l, r); // 建立边}cin >> k;for (int i = 1; i <= k; i++) {cin >> a[i];be[a[i]] = 1; // 标记为1,表示被摧毁}int ans = n-k; // 一开始的时候每个点都是一个块// 初始化并查集for (int i = 0; i <= n; i++) fa[i] = i;// 开始区分联通分量for (int i = 0; i < n; i++) {if (be[i]) continue;for (int u : edg[i]) {if (be[u]) continue;if (find(i) == find(u)) continue;uni(i, u);// 连接ans--;}}daan[k+1] = ans;for (int i = k; i >= 1; i--) {//cout << "yes" << endl;int xiufu = a[i];ans++;be[xiufu] = 0; // 恢复为1for (int u : edg[xiufu]) {if (be[u]) continue;if (find(u) == find(xiufu)) continue;ans--;uni(u, xiufu);}daan[i] = ans;}for (int i = 1; i <= k+1; i++) {cout << daan[i] << endl;}//cout << " now";return 0;
}
相关文章:
并查集进阶版
过关代码如下 #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc.h> #include<unordered_set> using namespace std;int n, m; vector<int> edg[400005]; int a[400005], be[400005]; // a的作用就是存放要摧毁 int k; int fa[400005]; int daan[400005]…...
贪心(不相交的开区间、区间选点、带前导的拼接最小数问题)
目录 1.简单贪心 2.区间贪心 不相交的开区间 1.如何删除? 2.如何比较大小 区间选点问题 3.拼接最小数 1.简单贪心 比如:给你一堆数,你来构成最大的几位数 2.区间贪心 不相交的开区间 思路: 首先,如果有两个…...
[力扣题解] 617. 合并二叉树
题目:617. 合并二叉树 思路 递归法遍历,随便一种遍历方式都可以,以前序遍历为例; 代码 class Solution { public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 NULL){return root2;}if(root2 NULL){r…...
kafka-消费者组(SpringBoot整合Kafka)
文章目录 1、消费者组1.1、使用 efak 创建 主题 my_topic1 并建立6个分区并给每个分区建立3个副本1.2、创建生产者发送消息1.3、application.yml配置1.4、创建消费者监听器1.5、创建SpringBoot启动类1.6、屏蔽 kafka debug 日志 logback.xml1.7、引入spring-kafka依赖1.8、消费…...
Redisson知识
使用Redission获取锁 RLock lock redisson.getLock("my-lock"); 一、Redisson使用不指定锁过期时间的方式加锁: lock.lock(); 特点: 1.使用Redisson加的锁,具有自动续期机制,如果业务运行时间较长,运行…...
0103__【C/C++ 单线程性能分析工具 Gprof】 GNU的C/C++ 性能分析工具 Gprof 使用全面指南
【C/C 单线程性能分析工具 Gprof】 GNU的C/C 性能分析工具 Gprof 使用全面指南-CSDN博客...
如何把几个pdf文件合成在一个pdf文件
PDF合并,作为一种常见的文件处理方式,无论是在学术研究、工作汇报还是日常生活中,都有着广泛的应用。本文将详细介绍PDF合并的多种方法,帮助读者轻松掌握这一技能。 打开 “轻云处理pdf官网” 的网站,然后上传pdf。 pd…...
Stream与MLC测试CPU内存DDR5的原理与方法详解
在高性能计算和服务器领域,内存性能是决定整体系统性能的关键因素之一,特别是随着DDR5内存的普及,其更高的带宽和更低的延迟特性使得内存性能测试变得更加重要。本文将详细介绍使用Stream和MLC两种工具对CPU内存DDR5进行性能测试的原理和实施…...
linux业务代码性能优化点
planning优化的一些改动----------> 减少值传递,多用引用来传递 <---------- // ----------> 减少值传递,多用引用来传递 <---------- // 例1: class A{}; std::vector<A> v; // for(auto elem : v) {} // 不建议ÿ…...
Shell脚本学习_字符串变量
目录 1.Shell字符串变量:格式介绍 2.Shell字符串变量:拼接 3.Shell字符串变量:字符串截取 4.Shell索引数组变量:定义-获取-拼接-删除 1.Shell字符串变量:格式介绍 1、目标: 能够使用字符串的三种方式 …...
spring-kafka-生产者服务搭建测试(SpringBoot整合Kafka)
文章目录 1、生产者服务搭建1.1、引入spring-kafka依赖1.2、application.yml配置----v1版1.3、使用Java代码创建主题分区副本1.4、发送消息 1、生产者服务搭建 1.1、引入spring-kafka依赖 <?xml version"1.0" encoding"UTF-8"?> <project xml…...
JVM学习-内存泄漏
内存泄漏的理解和分类 可达性分析算法来判断对象是否是不再使用的对象,本质都是判断一上对象是否还被引用,对于这种情况下,由于代码的实现不同就会出现很多内存泄漏问题(让JVM误以为此对象还在引用,无法回收,造成内存泄…...
Go微服务: 分布式之通过本地消息实现最终一致性和最大努力通知方案
通过本地消息实现最终一致性 1 )概述 我们的业务场景是可以允许我们一段时间有不一致的消息的状态的,并没有说必须特别高的这个消息的一致性比如说在TCC这个架构中,如果采用了消息的最终一致性,整体架构设计要轻松好多即便我们库…...
BC C language
题目汇总 No.1 打印有规律的字符(牛牛的字符菱形) 代码展示 #include<stdio.h> int main() {char ch0;scanf("%c",&ch);for(int i0;i<5;i){for(int j0;j<5;j){if((i0||i4)&&j2)printf("%c", ch);else if ((i 1||i3) &&…...
算法训练营第四十九天 | LeetCode 139单词拆分
LeetCode 139 单词拆分 基本还是完全背包的思路,不过用了三重循环,第三重循环是用于判断当前字符串尾部指定长度字符是否和列表中某一字符串相同,是的话可以将当前dp[j]或上当前下标减去该单词长度后的下标值。 代码如下: clas…...
阿里云一键登录号码认证服务
阿里云文档:号码认证SDK_号码认证服务(PNVS)-阿里云帮助中心 对于后端大概流程 前端App会传一个token过来 后端通过下面方法解析 如果解析可以获得号码,说明号码认证成功,如果无法正确解析则认证失败 /*** actoken来换取电话号码* param token app端用户授权actok…...
【UML用户指南】-05-对基本结构建模-类
目录 1、名称(name) 2、属性 (attribute) 3、操作(operation) 4、对属性和操作的组织 4.1、衍型 4.2、职责 (responsibility) 4.3、其他特征 4.4、对简单类型建模 5、结构良…...
【C++ 初阶】引用 () 实际的一些用法、常引用问题 详解!
文章目录 1. 常引用的背景2. 字符 a 与 整形 97 是相同的,但是具体是怎么比较的呢 ? 1. 常引用的背景 注意: 🐧① 权限可以平移、可以缩小,但是权限 不可以放大。 🐧 类型转换中间会产生临时变量 2. 字…...
adb dump当前可见的窗口
1、窗口信息 adb shell dumpsys window windows > w.txt2、dump当前可见的窗口activity windows系统 adb shell dumpsys activity | findStr mFocusmac系统 adb shell dumpsys activity | grep mFocus3、dump当前处于栈顶的activity windows系统 adb shell dumpsys activi…...
Java Web学习笔记27——对话框、表单组件
常见组件对话框: Dialog对话框:在保留当前页面状态下,告知用户并承载相关操作。 dialogTableVisible: false 默认是不可见的。 在按钮属性中设置为true的意思,点击按钮的时候,才会true,对话框才会显示。 …...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
WEB3全栈开发——面试专业技能点P4数据库
一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库,基于 mysql 库改进而来,具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点: 支持 Promise / async-await…...
