当前位置: 首页 > news >正文

并查集进阶版

在这里插入图片描述
在这里插入图片描述
过关代码如下

#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.如何删除&#xff1f; 2.如何比较大小 区间选点问题 3.拼接最小数 1.简单贪心 比如&#xff1a;给你一堆数&#xff0c;你来构成最大的几位数 2.区间贪心 不相交的开区间 思路&#xff1a; 首先&#xff0c;如果有两个…...

[力扣题解] 617. 合并二叉树

题目&#xff1a;617. 合并二叉树 思路 递归法遍历&#xff0c;随便一种遍历方式都可以&#xff0c;以前序遍历为例&#xff1b; 代码 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使用不指定锁过期时间的方式加锁&#xff1a; lock.lock(); 特点&#xff1a; 1.使用Redisson加的锁&#xff0c;具有自动续期机制&#xff0c;如果业务运行时间较长&#xff0c;运行…...

0103__【C/C++ 单线程性能分析工具 Gprof】 GNU的C/C++ 性能分析工具 Gprof 使用全面指南

【C/C 单线程性能分析工具 Gprof】 GNU的C/C 性能分析工具 Gprof 使用全面指南-CSDN博客...

如何把几个pdf文件合成在一个pdf文件

PDF合并&#xff0c;作为一种常见的文件处理方式&#xff0c;无论是在学术研究、工作汇报还是日常生活中&#xff0c;都有着广泛的应用。本文将详细介绍PDF合并的多种方法&#xff0c;帮助读者轻松掌握这一技能。 打开 “轻云处理pdf官网” 的网站&#xff0c;然后上传pdf。 pd…...

Stream与MLC测试CPU内存DDR5的原理与方法详解

在高性能计算和服务器领域&#xff0c;内存性能是决定整体系统性能的关键因素之一&#xff0c;特别是随着DDR5内存的普及&#xff0c;其更高的带宽和更低的延迟特性使得内存性能测试变得更加重要。本文将详细介绍使用Stream和MLC两种工具对CPU内存DDR5进行性能测试的原理和实施…...

linux业务代码性能优化点

planning优化的一些改动----------> 减少值传递&#xff0c;多用引用来传递 <---------- // ----------> 减少值传递&#xff0c;多用引用来传递 <---------- // 例1&#xff1a; class A{}; std::vector<A> v; // for(auto elem : v) {} // 不建议&#xff…...

Shell脚本学习_字符串变量

目录 1.Shell字符串变量&#xff1a;格式介绍 2.Shell字符串变量&#xff1a;拼接 3.Shell字符串变量&#xff1a;字符串截取 4.Shell索引数组变量&#xff1a;定义-获取-拼接-删除 1.Shell字符串变量&#xff1a;格式介绍 1、目标&#xff1a; 能够使用字符串的三种方式 …...

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学习-内存泄漏

内存泄漏的理解和分类 可达性分析算法来判断对象是否是不再使用的对象&#xff0c;本质都是判断一上对象是否还被引用&#xff0c;对于这种情况下&#xff0c;由于代码的实现不同就会出现很多内存泄漏问题(让JVM误以为此对象还在引用&#xff0c;无法回收&#xff0c;造成内存泄…...

Go微服务: 分布式之通过本地消息实现最终一致性和最大努力通知方案

通过本地消息实现最终一致性 1 &#xff09;概述 我们的业务场景是可以允许我们一段时间有不一致的消息的状态的&#xff0c;并没有说必须特别高的这个消息的一致性比如说在TCC这个架构中&#xff0c;如果采用了消息的最终一致性&#xff0c;整体架构设计要轻松好多即便我们库…...

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 单词拆分 基本还是完全背包的思路&#xff0c;不过用了三重循环&#xff0c;第三重循环是用于判断当前字符串尾部指定长度字符是否和列表中某一字符串相同&#xff0c;是的话可以将当前dp[j]或上当前下标减去该单词长度后的下标值。 代码如下&#xff1a; clas…...

阿里云一键登录号码认证服务

阿里云文档&#xff1a;号码认证SDK_号码认证服务(PNVS)-阿里云帮助中心 对于后端大概流程 前端App会传一个token过来 后端通过下面方法解析 如果解析可以获得号码,说明号码认证成功,如果无法正确解析则认证失败 /*** actoken来换取电话号码* param token app端用户授权actok…...

【UML用户指南】-05-对基本结构建模-类

目录 1、名称&#xff08;name&#xff09; 2、属性 &#xff08;attribute&#xff09; 3、操作&#xff08;operation&#xff09; 4、对属性和操作的组织 4.1、衍型 4.2、职责 &#xff08;responsibility&#xff09; 4.3、其他特征 4.4、对简单类型建模 5、结构良…...

【C++ 初阶】引用 () 实际的一些用法、常引用问题 详解!

文章目录 1. 常引用的背景2. 字符 a 与 整形 97 是相同的&#xff0c;但是具体是怎么比较的呢 &#xff1f; 1. 常引用的背景 注意&#xff1a; &#x1f427;① 权限可以平移、可以缩小&#xff0c;但是权限 不可以放大。 &#x1f427; 类型转换中间会产生临时变量 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——对话框、表单组件

常见组件对话框&#xff1a; Dialog对话框&#xff1a;在保留当前页面状态下&#xff0c;告知用户并承载相关操作。 dialogTableVisible: false 默认是不可见的。 在按钮属性中设置为true的意思&#xff0c;点击按钮的时候&#xff0c;才会true&#xff0c;对话框才会显示。 …...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...