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

《蓝桥杯每日一题》并查集·AcWing1249. 亲戚

1.题目描述

或许你并不知道,你的某个朋友是你的亲戚。

他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。

如果能得到完整的家谱,判断两个人是否是亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及。

在这种情况下,最好的帮手就是计算机。

为了将问题简化,你将得到一些亲戚关系的信息,如Marry和Tom是亲戚,Tom和Ben是亲戚,等等。

从这些信息中,你可以推出Marry和Ben是亲戚。

请写一个程序,对于我们的关于亲戚关系的提问,以最快的速度给出答案。

输入格式

输入由两部分组成。

第一部分以 N,M 开始。N 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N。下面有 M 行,每行有两个数 ai,bi,表示已知 aibi是亲戚。

第二部分以 Q开始。以下 Q 行有 Q 个询问,每行为 ci,di,表示询问 cidi 是否为亲戚。

输出格式

对于每个询问 ci,di,输出一行:若 cidi 为亲戚,则输出“Yes”,否则输出“No”。

数据范围

1≤N≤20000

1≤M≤10的六次方

1≤Q≤10的六次方

输入样例:

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

输出样例:

Yes
No
Yes

2.思路分析

我们先初始化p数组

然后输入m个数

我们查询一下,如果root1(find(a),即a的根节点)不是root2(find(b),即b的根节点),我们就把它们连接起来

最后输入q个数判断一下就行了,如果它们都是一个祖宗,我们就输出Yes,反之输出No

注意用BufferedReader和BufferedWriter优化一下输入输出,不然会超时

关于快速输入可以看一下我的这篇博客

https://blog.csdn.net/m0_68055637/article/details/128551437

3.Ac代码

import java.io.*;public class Main {static int N=20010;static int []p=new int[N]; //存储每个点的祖宗节点public static void main(String[] args) throws IOException {BufferedReader  br=new BufferedReader(new InputStreamReader(System.in));BufferedWriter  bw=new BufferedWriter(new OutputStreamWriter(System.out));String []s=br.readLine().split(" ");int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]);for (int i = 0; i < n; i++) {p[i]=i;}while (m-->0){s=br.readLine().split(" ");int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]);int root1=find(a),root2=find(b); //分别找到两个人的祖宗节点,并判断是不是亲戚if(root1!=root2)  p[root1]=root2;      //如果不是,添加至同族}int t=Integer.parseInt(br.readLine());while (t-->0){s=br.readLine().split(" ");int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]);bw.write(find(a)==find(b)?"Yes":"No");bw.newLine(); //换行}bw.flush();  //输出缓冲区才能输出}private static int find(int x) {if(p[x]!=x)  p[x]=find(p[x]);return p[x];}
}
感谢你能看完, 如有错误欢迎评论指正,有好的思路可以交流一波,如果对你有帮助的话,点个赞支持下

相关文章:

《蓝桥杯每日一题》并查集·AcWing1249. 亲戚

1.题目描述或许你并不知道&#xff0c;你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱&#xff0c;判断两个人是否是亲戚应该是可行的&#xff0c;但如果两个人的最近公共祖先与他们相隔好几代&#xff0c;使得家谱十分庞…...

亚马逊云科技依托人工智能进行游戏数据分析,解决游戏行业痛点,助力游戏增长

前言 据互联网数据显示&#xff1a;2014 年我国游戏行业用户规模为 517.31 百万人&#xff0c;直至 2020 年达 554.79 百万人&#xff1b;同时&#xff0c;2020 年&#xff0c;我国游戏市场实际销售收入 2786.87 亿元&#xff0c;比 2019 年增加了478.1 亿元&#xff0c…...

为什么不建议用 equals 判断对象相等?

一直以为这个方法是java8的&#xff0c;今天才知道是是1.7的时候&#xff0c;然后翻了一下源码。 这片文章中会总结一下与a.equals(b)的区别&#xff0c;然后对源码做一个小分析。 一&#xff0c;值是null的情况&#xff1a; 1.a.equals(b), a 是null, 抛出NullPointExcepti…...

手写线程池实例并测试

前言&#xff1a;在之前的文章中介绍过线程池的核心原理&#xff0c;在一次面试中面试官让手写线程池&#xff0c;这块知识忘记的差不多了&#xff0c;因此本篇文章做一个回顾。 希望能够加深自己的印象以及帮助到其他的小伙伴儿们&#x1f609;&#x1f609;。 如果文章有什么…...

实操go开发环境的配置

1、Go 安装包下载&#xff0c;下载地址如下&#xff1a; go语言中文网下载&#xff08;本人电脑的系统是Windows&#xff0c;这里以Windows版本的安装包为例&#xff0c;安装就是傻瓜式安装&#xff0c;只要点下一步–下一步–完成就可以了&#xff0c;本人安装在C盘下。 我…...

华为OD机试真题Python实现【匿名信】真题+解题思路+代码(20222023)

匿名信 题目 电视剧《分界线》里面有一个片段,男主为了向警察透露案件细节,且不暴露自己,于是将报刊上的字减下来,剪拼成匿名信。 现在又一名举报人,希望借鉴这种手段,使用英文报刊完成举报操作。 但为了增加文章的混淆度,只需满足每个单词中字母数量一致即可,不关注…...

阿里淘系面试经历(一)

文章目录 1、JVM讲一下,尽你所知道的1. 类的加载过程1.1 加载过程介绍1.2 类加载流程1.3 类加载器2. 垃圾回收2.1 如何确定对象已死2.2 垃圾回收算法2.2.1 标记--清除算法2.2.2 复制算法2.2.3 标记--整理算法2.3 垃圾收集器2.3.1 Serial 收集器2.3.2 ParNew 收集器2.3.3 Paral…...

matplotlib绘制三维图

目录线状堆积图 PolygonPlot三维表面图 SurfacePlot散点图ScatterPlot柱形图 BarPlot三维直方图螺旋曲线图 LinePlotContourPlot轮廓图网状图 WireframePlot箭头图二维三维合并文本图Text三维多个子图线状堆积图 PolygonPlot Axes3D.add_collection3d(col, zs0, zdir‘z’)  …...

4万字c++讲解+区分c和c++,不来可惜了(含代码+解析)

目录 1 C简介 1.1 起源 1.2 应用范围 1.3 C和C 2开发工具 3 基本语法 3.1 注释 3.2关键字 3.3标识符 4 数据类型 4.1基本数据类型 4.2 数据类型在不同系统中所占空间大小 4.3 typedef声明 4.4 枚举类型 5 变量 5.1 变量的声明和定义 5.2 变量的作用域 6 运算符…...

AcWing 482. 合唱队形

482. 合唱队形N 位同学站成一排&#xff0c;音乐老师要请其中的 (N−K) 位同学出列&#xff0c;使得剩下的 K 位同学排成合唱队形。     合唱队形是指这样的一种队形&#xff1a;设 K位同学从左到右依次编号为 1&#xff0c;2…&#xff0c;K&#xff0c;他们的身高分别为…...

Pytorch深度学习实战3-4:通俗理解张量Tensor的爱因斯坦求和(附实例)

目录1 爱因斯坦求和由来2 爱因斯坦求和原理3 实例&#xff1a;字母表示法3.1 向量运算3.2 矩阵运算3.3 张量运算4 实例&#xff1a;常量表示法4.1 向量运算4.2 矩阵运算4.3 张量运算1 爱因斯坦求和由来 爱因斯坦求和约定(Einstein summation convention)是一种标记的约定&#…...

GEE学习笔记 五十六:GEE中如何把文件导出到Google Drive的子目录

今天在群里看到有人在问一个问题&#xff0c;如何使用GEE把文件导出到Google Drive的子目录中&#xff1f;这里我就简单的说一下这个问题。 首先&#xff0c;在GEE中我们都知道了如何将数据导出导出Google Drive的文件夹中&#xff0c;如下面的一个例子&#xff1a; var geome…...

【Go基础】数据库编程

文章目录1. SQL语法简介2. MySQL最佳实践3. Go SQL驱动接口解读4. 数据库增删改查5. stmt6. SQLBuilder6.1 Go-SQLBuilder6.2 Gendry6.3 自行实现SQLBuilder7. GORM8. Go操作MongoDB1. SQL语法简介 SQL&#xff08;Structured Query Language&#xff09;是一套语法标准&#…...

【颠覆软件开发】华为自研IDE!未来IDE将不可预测!

IDE是软件开发生态的入口&#xff0c;但目前我们所使用的IDE基本都是由国外巨头提供&#xff0c;比如Visual Studio、Eclipse、JetBrains。这些IDE具有很高的断供风险&#xff0c;与操作系统、芯片、编程语言一样&#xff0c;非常重要。 随着越来越多的软件开始采用云上开发模…...

怎样从零基础学黑客

可以说想学黑客技术&#xff0c;要求你首先是一个“T”字型人才&#xff0c;也就是说电脑的所有领域你都能做的来&#xff0c;而且有一项是精通的。因此作为一个零基础的黑客爱好者来说&#xff0c;没有良好的基础是绝对不行的&#xff0c;下面我就针对想真正学习黑客的零基础朋…...

burp小程序抓包

身为一名码农&#xff0c;抓包肯定是一项必备技能。工作中遇到很多次需要对小程序进行抓包排查问题。下面分享一下我的抓包方式&#xff0c;使用的是电脑版小程序抓包&#xff0c;跟手机的方式都差不多的。 一、环境 微信版本&#xff1a;3.6.0.18 Burpsuite版本&#xff1a…...

文件上传攻击骚操作

允许直接上传shell 只要有文件上传功能&#xff0c;那么就可以尝试上传webshell直接执行恶意代码&#xff0c;获得服务器权限&#xff0c;这是最简单也是最直接的利用。 允许上传压缩包 如果可以上传压缩包&#xff0c;并且服务端会对压缩包解压&#xff0c;那么就可能存在Zip …...

Scala流程控制(第四章:分支控制、嵌套分支、switch分支、for循环控制全、while与do~while、多重与中断)

文章目录第 4 章 流程控制4.1 分支控制 if-else4.1.1 单分支4.1.2 双分支4.1.3 多分支4.2 嵌套分支4.3 Switch 分支结构4.4 For 循环控制4.4.1 范围数据循环&#xff08;To&#xff09;4.4.2 范围数据循环&#xff08;Until&#xff09;4.4.3 循环守卫4.4.4 循环步长4.4.5 嵌套…...

华为OD机试真题Python实现【整理扑克牌】真题+解题思路+代码(20222023)

整理扑克牌 题目 给定一组数字,表示扑克牌的牌面数字,忽略扑克牌的花色,请安如下规则对这一组扑克牌进行整理。 步骤一: 对扑克牌进行分组,规则如下 当牌面数字相同张数大于等于4时,组合牌为炸弹;三张相同牌面数字+两张相同牌面数字,且三张牌与两张牌不相同时,组合牌…...

【春秋云境】CVE-2022-28525

靶标介绍&#xff1a; ​ ED01-CMS v20180505 存在任意文件上传漏洞 打开靶场&#xff1a; 盲猜一波弱密码admin:admin就进去了。登录后在图中位置点击进行图片更新&#xff0c;需要将密码等都写上 抓包将图片信息进行替换&#xff0c;并修改文件名&#xff1a; POST /admin…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...

dvwa11——XSS(Reflected)

LOW 分析源码&#xff1a;无过滤 和上一关一样&#xff0c;这一关在输入框内输入&#xff0c;成功回显 <script>alert(relee);</script> MEDIUM 分析源码&#xff0c;是把<script>替换成了空格&#xff0c;但没有禁用大写 改大写即可&#xff0c;注意函数…...