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

并查集学习心得

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.前言&#xff1a; 最近在学习自动驾驶方向的东西&#xff0c;简单整理一些学习笔记&#xff0c;学习过程中发现宝藏up 手写AI 1. 概述 Laneaf思想是把后处理放在模型里面。重点在于理解vaf&#xff0c; haf&#xff0c;就是横向聚类&#xff1a;中心点&#xff0c;纵向聚类&…...

软考系统架构之案例篇(Redis相关概念)

案例篇-Redis相关概念 1. Redis与Memcache能力对比2. Redis集群切片的常见方式3. Redis分布式存储方案4. Redis数据分片方案5. Redis持久化 1. Redis与Memcache能力对比 工作MemCacheRedis数据类型简单 key/value 结构丰富的数据结构持久性不支持支持分布式存储客户端哈希分片…...

黑客入门指南,学习黑客必须掌握的技术

黑客一词&#xff0c;原指热心于计算机技术&#xff0c;水平高超的电脑专家&#xff0c;尤其是程序设计人员。是一个喜欢用智力通过创造性方法来挑战脑力极限的人&#xff0c;特别是他们所感兴趣的领域&#xff0c;例如电脑编程等等。 提起黑客&#xff0c;总是那么神秘莫测。在…...

定档11月2日,YashanDB 2023年度发布会完整议程公布

数据库作为支撑核心业务的关键技术&#xff0c;对数字经济的发展有着重要的支撑作用&#xff0c;随着云计算、AI等技术的迅猛发展和数据量的爆发式增长&#xff0c;推动着数据库技术的加速创新。 为了应对用户日益复杂的数据管理需求&#xff0c;赋能行业国产化建设和数字化转型…...

composer安装thinkphp6报错

composer安装thinkphp6报错&#xff0c; 查看是否安装了对应的PHP扩展&#xff0c;我这边使用的是宝塔的环境&#xff0c;全程可以可视化操作 这样就可以安装完成了...

此页面不能正确地重定向

这种是由于条件判断有误&#xff0c;程序不断的重定向到一个页面&#xff0c;而造成的死循环的情况 下面列举一个常出现的场景之一 1、使用过滤器实现登录验证错误处理 解释&#xff1a;当用户访问login.jsp进行登录的时候&#xff0c;这个时候请求会被Filter捕获&#xff0…...

【Apache Flink】实现有状态函数

文章目录 在RuntimeContext 中声明键值分区状态通过ListCheckPonitend 接口实现算子列表状态使用CheckpointedFunction接口接收检查点完成通知参考文档 在RuntimeContext 中声明键值分区状态 Flink为键值分区状态&#xff08;Keyed State&#xff09;提供了几种不同的原语&…...

Android原生项目集成uniMPSDK(Uniapp)遇到的报错总结

uni小程s序SDK 集成到Android原生项目:老项目中用到的库较多&#xff0c;会出现几种冲突问题&#xff0c;总结如下&#xff1a; 报错1&#xff1a; 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命令报错&#xff1a;cc 未找到命令&#xff0c;系统中缺少gcc&#xff0c;执行命令安装 gcc&#xff1a; yum -y install gcc automake autocon…...

在Win11上部署ChatGLM3详细步骤

023年10月27日&#xff0c;智谱AI于2023中国计算机大会&#xff08;CNCC&#xff09;上&#xff0c;推出了全自研的第三代基座大模型ChatGLM3及相关系列产品&#xff0c;这也是智谱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集群&#xff0c;以及怎么在SpringBoot项目中使用Kafka。 kafka集群环境包地址&#xff1a;百度网盘 请输入提取码 提取码&#xff1a;x9yn 一、Kafka集群搭建 1、准备环境 &#xff08;1&#xff09;准备三台…...

一个简单的注册的页面,如有错误请指正;(3.JavaScript)

这段代码是一个JavaScript函数&#xff0c;实现了用户登录和上传图片的功能&#xff0c;并包含了一些辅助函数。让我一一解释&#xff1a; 1. login()&#xff1a;这个函数用于登录操作。首先&#xff0c;通过$(#name).val()来获取ID为name的元素的值&#xff0c;同理获取其他…...

selenium (自动化概念 测试环境配置)

什么是自动化测试 自动化测试介绍 自动化测试指软件测试的自动化&#xff0c;在预设状态下运行应用程序或者系统. 预设条件包括正常和异常&#xff0c;最后评估运行结果。   自动化测试&#xff0c;就是将人为驱动的测试行为转化为机器执行的过程。 【机器 代替 人工】 自动化…...

Mybatis-Plus(企业实际开发应用)

一、Mybatis-Plus简介 MyBatis-Plus是MyBatis框架的一个增强工具&#xff0c;可以简化持久层代码开发MyBatis-Plus&#xff08;简称 MP&#xff09;是一个 MyBatis 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生。 官网&a…...

Spring Web MVC入门

一&#xff1a;了解Spring Web MVC (1)关于Java开发 &#x1f31f;Java开发大多数场景是业务开发 比如说京东的业务就是电商卖货、今日头条的业务就推送新闻&#xff1b;快手的业务就是短视频推荐 (2)Spring Web MVC的简单理解 &#x1f497;Spring Web MVC&#xff1a;如何使…...

【C++】mapset的底层结构 -- AVL树(高度平衡二叉搜索树)

前面我们对 map / multimap / set / multiset 进行了简单的介绍&#xff0c;可以发现&#xff0c;这几个容器有个共同点是&#xff1a;其底层都是按照二叉搜索树来实现的。 但是二叉搜索树有其自身的缺陷&#xff0c;假如往树中插入的元素有序或者接近有序&#xff0c;二叉搜索…...

吴恩达《机器学习》1-4:无监督学习

一、无监督学习 无监督学习就像你拿到一堆未分类的东西&#xff0c;没有标签告诉你它们是什么&#xff0c;然后你的任务是自己找出它们之间的关系或者分成不同的组&#xff0c;而不依赖于任何人给你关于这些东西的指导。 以聚类为例&#xff0c;无监督学习算法可以将数据点分成…...

一个简单的注册页面,如有错误请指正(2.css)

这段CSS代码定义了页面的样式&#xff0c;让我逐个解释其功能&#xff1a; 1. * {}&#xff1a;通配符选择器&#xff0c;用于将页面中的所有元素设置统一的样式。这里将margins和paddings设置为0&#xff0c;以去除默认的边距。 2. div img {}&#xff1a;选择页面中所有div…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...