【并查集】专题练习
题目列表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
模板
836. 合并集合 - AcWing题库
#include<bits/stdc++.h>
using ll=long long;
//#define int ll
const int N=1e5+10,mod=1e9+7;
int n,m;
int p[N],sz[N];
int find(int a)
{if(p[a]!=a) p[a]=find(p[a]);return p[a];
}
void merge(int a,int b)
{int pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;sz[pb]+=sz[pa];}
}
void que(int a,int b){if(find(a)==find(b)) std::cout<<"Yes"<<'\n';else std::cout<<"No"<<'\n';
}
void solve()
{std::cin>>n>>m;for(int i=1;i<=n;i++){sz[i]=1;p[i]=i;}while(m--){char op;int a,b;std::cin>>op>>a>>b;if(op=='M'){merge(a,b);}else{que(a,b);}}}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}
837. 连通块中点的数量 - AcWing题库
#include<bits/stdc++.h>
const int N=1e5+10;
int p[N];
int size[N];
int find(int x)
{if(x!=p[x]){p[x]=find(p[x]);}return p[x];
}
void merge(int a,int b)
{int pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;size[pb]+=size[pa];}
}
void query(int a,int b)
{int pa=find(a),pb=find(b);if(pa==pb){std::cout<<"Yes"<<'\n';}else std::cout<<"No"<<'\n';
}
void solve()
{int n,m;std::cin>>n>>m;for(int i=1;i<=n;i++){p[i]=i;size[i]=1;}while(m--){char op[5];std::cin>>op;int a,b;if(op[0]=='C') {std::cin>>a>>b;merge(a,b);}else if(op[1]=='1'){std::cin>>a>>b;query(a,b);}else{std::cin>>a;//询问a中连通块点的个数std::cout<<size[find(a)]<<'\n';}}
}
signed main()
{int t=1;//std::cin>>t;while(t--){solve();}return 0;
}
240. 食物链 - AcWing题库
普及-
(合并集合)(P2256 一中校运会之百米跑 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
判断点是否在一个集合中。
#include<bits/stdc++.h>using ll=long long;
using ull=unsigned long long;#define fir first
#define sec second
#define int llconst int N=2e4+10;
const int mod=1e9+7;
const double eps=1e-6;
int n,m;
int p[N],sz[N];
ll find(int a)
{if(p[a]!=a) p[a]=find(p[a]);return p[a];
}
void merge(int a,int b)
{int pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;sz[pb]+=sz[pa];}
}
bool que(int a,int b)
{if(find(a)==find(b)) return true;else return false;
}
void solve()
{std::cin>>n>>m;std::map<std::string,int> mp;for(int i=1;i<=n;i++){std::string s;std::cin>>s;mp[s]=i;p[i]=i,sz[i]=1; } for(int i=1;i<=m;i++){std::string a,b;std::cin>>a>>b;merge(mp[a],mp[b]);}int k;std::cin>>k;while(k--){std::string a,b;std::cin>>a>>b;if(que(mp[a],mp[b])) std::cout<<"Yes.\n";else std::cout<<"No.\n";}
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}
(合并集合)P8396 [CCC2022 S2] Good Groups - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
还是个模板题
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
#define fir first
#define sec second
//#define int llconst int N=1e5+10;
const int mod=1e9+7;int n;
ll ans;
struct node{std::string s1,s2;
}a[N];
struct nod{std::string s1,s2;
}b[N];
std::unordered_map<std::string,std::string> p;std::string find(std::string& s)
{if(p[s]!=s) p[s]=find(p[s]);return p[s];
}
void merge(std::string& a,std::string& b)
{std::string pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;}
}
bool que(std::string& a,std::string& b)
{if(find(a)!=find(b)) return false;else return true;
}
void solve()
{int x;//每个组3个人std::cin>>x;
// getchar();for(int i=1;i<=x;i++){//getchar();std::cin>>a[i].s1>>a[i].s2;}int y;std::cin>>y; for(int i=1;i<=y;i++){//getchar();std::cin>>b[i].s1>>b[i].s2;}int g;std::cin>>g;for(int i=1;i<=g;i++){std::string a,b,c;//getchar();std::cin>>a>>b>>c;if(p.count(a)==0) p[a]=a;if(p.count(b)==0) p[b]=b;if(p.count(c)==0) p[c]=c;merge(a,b);merge(c,b);}ll ans=0;for(int i=1;i<=x;i++){if(!que(a[i].s1,a[i].s2)) ans++; }for(int i=1;i<=y;i++){if(que(b[i].s1,b[i].s2)) ans++; }std::cout<<ans<<'\n';
}
signed main()
{//freopen("a","w",stdout);//把结果输出到a.in里面 std::ios::sync_with_stdio(false);std::cin.tie(0);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}
相关文章:
【并查集】专题练习
题目列表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 模板 836. 合并集合 - AcWing题库 #include<bits/stdc.h> using lllong long; //#define int ll const int N1e510,mod1e97; int n,m; int p[N],sz[N]; int find(int a) {if(p[a]!a) p[a]find(p[a]);return p[a…...
服装连锁店收银系统需要具备的五大功能
当今服装连锁店在市场竞争中需要拥有高效的收银系统来提升业务效率和顾客满意度。以下是服装连锁店收银系统需要具备的五大功能: 首先,完善的商品管理功能是至关重要的。这包括商品信息的录入、管理、更新和查询。收银系统应该能够快速而准确地识别商品&…...
IMU状态预积分代码实现 —— IMU状态预积分类
IMU状态预积分代码实现 —— IMU状态预积分类 实现IMU状态预积分类 实现IMU状态预积分类 首先,实现预积分自身的结构。一个预积分类应该存储一下数据: 预积分的观测量 △ R ~ i j , △ v ~ i j , △ p ~ i j \bigtriangleup \tilde{R} _{ij},\bigtrian…...
C语言编程:探索最小公倍数的奥秘
C语言编程:探索最小公倍数的奥秘 在编程的世界中,计算两个数的最小公倍数(LCM)是一个常见的数学问题。C语言作为一种基础且强大的编程语言,为我们提供了实现这一功能的工具。本文将从四个方面、五个方面、六个方面和七…...
Java设计模式-活动对象与访问者
活动对象 Java设计模式中,活动对象是指一个对象始终处于活动的状态,该对象包括一个线程安全的数据结构以及一个活跃的执行线程。 如上所示,ActiveCreature类的构造函数初始化一个线程安全的数据结构(阻塞队列)、初始化…...
用HAL库改写江科大的stm32入门-6-3 PWM驱动LED呼吸灯
接线图: 2 :实验目的: 利用pwm实现呼吸灯。 关键PWM定时器设置: 代码部分: int main(void) {/* USER CODE BEGIN 1 *//* USER CODE END 1 *//* MCU Configuration--------------------------------------------------------*…...
[数据集][目标检测]喝水检测数据集VOC+YOLO格式995张3类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):995 标注数量(xml文件个数):995 标注数量(txt文件个数):995 标注类别…...
【C++】开源:RabbitMQ安装与配置使用(SimpleAmqpClient)
😏★,:.☆( ̄▽ ̄)/$:.★ 😏 这篇文章主要介绍。 无专精则不能成,无涉猎则不能通。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下,下次更新不迷路…...
git使用流程与规范
原文网址:git代码提交流程与规范-CSDN博客 简介 本文git提交流程与规范是宝贵靠谱的经验,它能解决如下问题: 分支差距过大,导致合代码无数的冲突合完代码后发现代码丢失分支不清晰,无法追溯问题合代码耗时很长&…...
力扣 264. 丑数 II python AC
堆 from heapq import heappop, heappushclass Solution:def nthUglyNumber(self, n):q [1]vis {1}for _ in range(n - 1):now heappop(q)for i in [2, 3, 5]:if now * i not in vis:vis.add(now * i)heappush(q, now * i)return heappop(q)...
resetlogs强制拉库失败并使用备份system文件还原数据库故障处理---惜分飞
接手一个库,在open的过程中遭遇到ORA-600 2662错误 Sun May 26 10:15:54 2024 alter database open RESETLOGS RESETLOGS is being done without consistancy checks. This may result in a corrupted database. The database should be recreated. RESETLOGS after incomplete…...
解析Java中1000个常用类:Error类,你学会了吗?
在 Java 编程中,异常处理是一个至关重要的部分。Java 提供了丰富的异常处理机制,包括 Exception 和 Error。 本文将深入探讨 Error 类的功能、用法、实际应用中的注意事项,以及如何处理和预防这些错误。 什么是 Error 类? Error 类是 Java 中 Throwable 类的一个子类,用…...
【C++】——string模拟实现
前言 string的模拟实现其实就是增删改查,只不过加入了类的概念。 为了防止与std里面的string冲突,所以这里统一用String。 目录 前言 一 初始化和销毁 1.1 构造函数 1.2 析构函数 二 迭代器实现 三 容量大小及操作 四 运算符重载 4.1 bool…...
unity2D跑酷游戏
项目成果 项目网盘 导入资源包 放入Assets文件Assets资源文件 游戏流程分析 摄像机size调小,让图片占满屏幕 人跑本质,相对运动,图片无限向右滚动 图片720,缩小100倍第二个图片x为7.2每unit px100两张图片刚好挨着连贯 空对象Bg…...
OWASP top10--SQL注入(四、sqlmap安装及使用)
目录 sqlmap工具安装: 工具说明: 主要功能特性包括: 基本使用示例: 先下载python2.7.9版本 sqlmap运行 sqlmap工具使用 -u -r –-levelLEVEL扫描深度级别 --riskRISK 执行测试的风险 -threads 线程数 -batch-smart智能…...
Java基础入门day62
day62 AJAX 概念 AJAX: Asynchronous Javascript And XML AJAX是一种无需重新加载整个网页的情况下,能够更新部分网页的技术 AJAX是一种用于创建快速动态网页的技术 通过在后台与服务器进行少量数据交换,AJAX可以使网页实现异步更新 传统…...
Oracle中两张表具有相同结构,如何将一张表内容全部插入到另一个表中
在Oracle中,如果两张表具有相同的结构,你可以使用INSERT INTO ... SELECT语句将一张表的内容插入到另一张表中。以下是一个示例: 假设有两个表:table1 和 table2,它们具有相同的列结构。要将 table1 的所有内容插入到…...
比特币的理论上限是多少个?
标签: 比特币的理论上限; 已经挖出多少个比特币; 问题:比特币的理论上限是多少个?截至2023年10月,已经挖出多少个比特币出来了? 比特币的理论上限 比特币的设计者中本聪在比特币协议中设定了比…...
LeetCode-131 分割回文串
LeetCode-131 分割回文串 题目描述解题思路C 代码 题目描述 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串。返回 s 所有可能的分割方案。 示例 1: 输入:s “aab” 输出:[[“a”,“a”,“b”],…...
Flutter 中的 SliverPrototypeExtentList 小部件:全面指南
Flutter 中的 SliverPrototypeExtentList 小部件:全面指南 Flutter 是一个功能强大的 UI 框架,由 Google 开发,允许开发者使用 Dart 语言构建跨平台的移动、Web 和桌面应用。在 Flutter 的丰富组件库中,SliverPrototypeExtentLis…...
NeuralForecast 推理 - 数据集从文件dataset.pkl读
NeuralForecast 推理 - 数据集从文件dataset.pkl读 flyfish from ray import tune from neuralforecast.core import NeuralForecast from neuralforecast.auto import AutoMLP from neuralforecast.models import NBEATS, NHITS import torch import torch.nn as nn import …...
TS-类型转换(显式)
1.将其他类型转换为布尔类型 要将其他类型转换为布尔类型,只需要将待转换的值传入Boolean()函数 var msg: string "ok"; var msgToBollean: boolean Boolean(msg); //得到trueBoolean()函数会判断传入的值是空值还是非空值。 若表示非空值࿰…...
protobufjs 配置踩坑记录
本文主要是小程序使用PB协议,以下时博主遇到的问题以及解决办法。 1、安装protobufjs npm install --save protobufjs 注意:我之前也使用过 npm install -g protobufjs去安装,但是出现以下的问题,关键是我使用sudo 清除相关文件…...
freeswitch官方仓库
概述 在使用源代码编译安装freeswitch的过程中,我们经常需要一些依赖库,其中freeswitch官方的yum源仓库是最齐全最方便的。 但是,freeswitch仓库的配置和使用需要先在signalwire网站注册账号并获取PAT(personal access token&am…...
element ui el-calendar日历组件完整代码
el-calendar日历组件完整代码 1. 说在前面2. 日历整体代码3. 编辑与新增 1. 说在前面 最近一直忙于上班,没咋看博客,发现很多小伙伴都要日历组件的代码,于是今天抽空给大家整理一下,为爱发电!日历组件的原文在这里&am…...
初识java——javaSE(8)异常
文章目录 一 异常的概念与体系结构1.1 什么是异常?1.2 异常的体系结构!1.3 编译时异常与运行时异常与Error编译时异常:异常声明:throws关键字 运行时异常:什么是Error? 二 处理异常2.1 异常的抛出:throw(注…...
C语言面试题11至20题
探索编程面试题:深度解析11至20题 在编程面试中,经常会遇到一些需要深入理解计算机科学基础和编程原理的问题。以下是对一些常见面试题的详细解答,涵盖递归、循环控制、内存管理等关键概念。 11. 递归函数定义没有问题,递归深层…...
视频汇聚EasyCVR综合安防平台对接GA/T1400公安视图库及应用方案
随着科技的不断进步,视频监控系统在公共安全领域发挥着越来越重要的作用。GA/T1400公安视图库作为公安视频图像信息应用系统的标准,为视频监控系统的对接提供了统一的规范和技术要求。 GA/T1400标准的应用范围广泛,涵盖了公安系统的视频图像信…...
在Github找自己想要的的项目
点击进入github 1.首先进入到github的首页;搜索框搜(先关键字搜索)in:name 你的找的项目 比如: in:name Sping Boot2.进一步检索(点赞数高的) in:name Sping Boot star:>1000 3.如何要找最新的&…...
第16篇:JTAG UART IP应用<三>
Q:如何通过HAL API函数库访问JTAG UART? A:Quartus硬件工程以及Platform Designer系统也和第一个Nios II工程--Hello_World的Quartus硬件工程一样。 Nios II软件工程对应的C程序调用HAL API函数,如open用于打开和创建文件&#…...
Python——Selenium快速上手+方法(一站式解决问题)
目录 前言 一、Selenium是什么 二、Python安装Selenium 1、安装Selenium第三方库 2、下载浏览器驱动 3、使用Python来打开浏览器 三、Selenium的初始化 四、Selenium获取网页元素 4.1、获取元素的实用方法 1、模糊匹配获取元素 & 联合多个样式 2、使用拉姆达表达式 3、加上…...
2024最新群智能优化算法:大甘蔗鼠算法(Greater Cane Rat Algorithm,GCRA)求解23个函数,提供MATLAB代码
一、大甘蔗鼠算法 大甘蔗鼠算法(Greater Cane Rat Algorithm,GCRA)由Jeffrey O. Agushaka等人于2024年提出,该算法模拟大甘蔗鼠的智能觅食行为。 参考文献 [1]Agushaka J O, Ezugwu A E, Saha A K, et al. Greater Cane Rat Alg…...
苍穹外卖数据可视化
文章目录 1、用户统计2、订单统计3、销量排名Top10 1、用户统计 所谓用户统计,实际上统计的是用户的数量。通过折线图来展示,上面这根蓝色线代表的是用户总量,下边这根绿色线代表的是新增用户数量,是具体到每一天。所以说用户统计…...
AWS需要实名吗?
AWS作为全球领先的云计算服务提供商,对于实名认证有着严格的要求。实名认证是指用户在使用AWS服务时需要提供真实有效的个人身份信息,以便AWS能够对用户的身份进行验证和管理。对于AWS而言,实名认证是确保用户安全和服务质量的重要环节&#…...
Android下HWC以及drm_hwcomposer普法(下)
Android下HWC以及drm_hwcomposer普法(下) 引言 不容易啊,写到这里。经过前面的普法(上),我相信童鞋们对HWC和drm_hwcomposer已经有了一定的认知了。谷歌出品,必须精品。我们前面的篇章见分析到啥来了,对了分析到了HwcDisplay::in…...
【评价类模型】熵权法
1.客观赋权法: 熵权法是一种客观求权重的方法,所有客观求权重的模型中都要有以下几步: 1.正向化处理: 极小型指标:取值越小越好的指标,例如错误率、缺陷率等。 中间项指标:取值在某个范围内较…...
PG 窗口函数
一,简介 窗口函数也叫分析函数,也叫OLAP函数,通过partition by分组,这里的窗口表示范围,,可以不指定PARATITION BY,会将这个表当成一个大窗口。 二,应用场景 (1)用于分…...
冯喜运:5.31晚间黄金原油行情分析及尾盘操作策略
【黄金消息面分析】:周五(5月31日),最新发布的数据显示,美国4月核心PCE物价指数月率录得0.2%,低于预期(0.3%),经济学家认为,核心指数比整体指数更能反映通胀。除此之外,美…...
Vue 框选区域放大(纯JavaScript实现)
需求:长按鼠标左键框选区域,松开后放大该区域,继续框选继续放大,反向框选恢复原始状态 实现思路:根据鼠标的落点,放大要显示的内容(内层盒子),然后利用水平偏移和垂直偏…...
C#加密与java 互通
文章目录 前言对方接口签名要求我方对接思路1.RSA 加密2.AES256加密 完整的加密帮助类 前言 提示:这里可以添加本文要记录的大概内容: 在我们对接其他公司接口的时候,时常会出现对方使用的开发语言和我方使用的开发语言不同的情况ÿ…...
C#【进阶】特殊语法
特殊语法、值和引用类型 特殊语法 文章目录 特殊语法1、var隐式类型2、设置对象初始值3、设置集合初始值4、匿名类型5、可空类型6、空合并操作符7、内插字符串8、单句逻辑简略写法 值和引用类型1、判断值和引用类型2、语句块3、变量的生命周期4、结构体中的值和引用5、类中的值…...
c语言之向文件读写数据块
c语言需要向文件读写数据块需要用到fread语句和fwrite语句 fread语句的语法格式 fread(butter,size,count,fp) butter:读取的数据存入内存地址 size:读取的字节大小 count:读取数据的个数 fp:读取的文件指针 fwrite语句语法格式 fwrite(butter,size,count,fp…...
6键编程智能照明:编程指南与深度解析
6键编程智能照明:编程指南与深度解析 随着智能家居的普及,智能照明系统逐渐成为现代家庭不可或缺的一部分。而6键编程智能照明,以其高度的灵活性和个性化设置,受到了越来越多消费者的青睐。那么,如何对6键编程智能照明…...
sql server 中的6种约束
一、约束定义 约束是用于定义和实施表的规则和限制,以确保数据的完整性和一致性。 即对一张表中的属性操作进行限制。 二、约束分类 通过定义约束,可以对数据库中的数据进行限制,以下是常见的约束: 1. 主键约束(Pr…...
师彼长技以助己(2)产品思维
师彼长技以助己(2)产品思维 前言 我把产品思维称之为:人生底层的能力以及蹉跎别人还蹉跎自己的能力,前者说明你应该具备良好产品思维原因,后者是你没有好的产品思维去做产品带来的灾难。 人欲即天理 请大家谈谈看到这…...
Redis学习笔记【基础篇】
SQL vs NOSQL SQL(Structured Query Language)和NoSQL(Not Only SQL)是两种不同的数据库处理方式,它们在多个维度上有所差异,主要区别包括: 数据结构: SQL(关系型数据库)…...
【文献阅读】基于模型设计的汽车软件质量属性
参考文献:《基于模型设计满足汽车软件质量和快速交付的挑战》,深向科技在2024年MATLAB XEPO大会的演讲 Tips:KISS原则,全称为“Keep It Simple, Stupid”,直译为“保持简单,愚蠢的人也能懂”...
撸广告赚金币小游戏app开发
在app上投放广告有哪些注意事项? 在app上投放广告需要注意以下几个方面。 首先,要选择合适的广告形式。根据自己的需求和目标受众,选择合适的广告形式,如横幅广告、插屏广告、视频广告等。不同的广告形式适用于不同的场景和目标…...
海外高清短视频:四川京之华锦信息技术公司
海外高清短视频:探索世界的新窗口 在数字化时代的浪潮下,海外高清短视频成为了人们探索世界、了解异国风情的新窗口。四川京之华锦信息技术公司这些短视频以其独特的视角、丰富的内容和高清的画质,吸引了无数观众的目光,让人们足…...
16:00面试,16:08就出来了,问的问题有点变态。。。
从小厂出来,没想到在另一家公司又寄了。 到这家公司开始上班,加班是每天必不可少的,看在钱给的比较多的份上,就不太计较了。没想到8月一纸通知,所有人不准加班,加班费不仅没有了,薪资还要降40%…...