《蓝桥杯每日一题》并查集·AcWing1249. 亲戚
1.题目描述
或许你并不知道,你的某个朋友是你的亲戚。
他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。
如果能得到完整的家谱,判断两个人是否是亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及。
在这种情况下,最好的帮手就是计算机。
为了将问题简化,你将得到一些亲戚关系的信息,如Marry和Tom是亲戚,Tom和Ben是亲戚,等等。
从这些信息中,你可以推出Marry和Ben是亲戚。
请写一个程序,对于我们的关于亲戚关系的提问,以最快的速度给出答案。
输入格式
输入由两部分组成。
第一部分以 N,M 开始。N 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N。下面有 M 行,每行有两个数 ai,bi,表示已知 ai 和 bi是亲戚。
第二部分以 Q开始。以下 Q 行有 Q 个询问,每行为 ci,di,表示询问 ci 和 di 是否为亲戚。
输出格式
对于每个询问 ci,di,输出一行:若 ci和 di 为亲戚,则输出“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.题目描述或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱,判断两个人是否是亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞…...

亚马逊云科技依托人工智能进行游戏数据分析,解决游戏行业痛点,助力游戏增长
前言 据互联网数据显示:2014 年我国游戏行业用户规模为 517.31 百万人,直至 2020 年达 554.79 百万人;同时,2020 年,我国游戏市场实际销售收入 2786.87 亿元,比 2019 年增加了478.1 亿元,…...
为什么不建议用 equals 判断对象相等?
一直以为这个方法是java8的,今天才知道是是1.7的时候,然后翻了一下源码。 这片文章中会总结一下与a.equals(b)的区别,然后对源码做一个小分析。 一,值是null的情况: 1.a.equals(b), a 是null, 抛出NullPointExcepti…...

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

实操go开发环境的配置
1、Go 安装包下载,下载地址如下: go语言中文网下载(本人电脑的系统是Windows,这里以Windows版本的安装包为例,安装就是傻瓜式安装,只要点下一步–下一步–完成就可以了,本人安装在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 位同学站成一排,音乐老师要请其中的 (N−K) 位同学出列,使得剩下的 K 位同学排成合唱队形。 合唱队形是指这样的一种队形:设 K位同学从左到右依次编号为 1,2…,K,他们的身高分别为…...

Pytorch深度学习实战3-4:通俗理解张量Tensor的爱因斯坦求和(附实例)
目录1 爱因斯坦求和由来2 爱因斯坦求和原理3 实例:字母表示法3.1 向量运算3.2 矩阵运算3.3 张量运算4 实例:常量表示法4.1 向量运算4.2 矩阵运算4.3 张量运算1 爱因斯坦求和由来 爱因斯坦求和约定(Einstein summation convention)是一种标记的约定&#…...

GEE学习笔记 五十六:GEE中如何把文件导出到Google Drive的子目录
今天在群里看到有人在问一个问题,如何使用GEE把文件导出到Google Drive的子目录中?这里我就简单的说一下这个问题。 首先,在GEE中我们都知道了如何将数据导出导出Google Drive的文件夹中,如下面的一个例子: 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(Structured Query Language)是一套语法标准&#…...

【颠覆软件开发】华为自研IDE!未来IDE将不可预测!
IDE是软件开发生态的入口,但目前我们所使用的IDE基本都是由国外巨头提供,比如Visual Studio、Eclipse、JetBrains。这些IDE具有很高的断供风险,与操作系统、芯片、编程语言一样,非常重要。 随着越来越多的软件开始采用云上开发模…...

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

burp小程序抓包
身为一名码农,抓包肯定是一项必备技能。工作中遇到很多次需要对小程序进行抓包排查问题。下面分享一下我的抓包方式,使用的是电脑版小程序抓包,跟手机的方式都差不多的。 一、环境 微信版本:3.6.0.18 Burpsuite版本:…...
文件上传攻击骚操作
允许直接上传shell 只要有文件上传功能,那么就可以尝试上传webshell直接执行恶意代码,获得服务器权限,这是最简单也是最直接的利用。 允许上传压缩包 如果可以上传压缩包,并且服务端会对压缩包解压,那么就可能存在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 范围数据循环(To)4.4.2 范围数据循环(Until)4.4.3 循环守卫4.4.4 循环步长4.4.5 嵌套…...
华为OD机试真题Python实现【整理扑克牌】真题+解题思路+代码(20222023)
整理扑克牌 题目 给定一组数字,表示扑克牌的牌面数字,忽略扑克牌的花色,请安如下规则对这一组扑克牌进行整理。 步骤一: 对扑克牌进行分组,规则如下 当牌面数字相同张数大于等于4时,组合牌为炸弹;三张相同牌面数字+两张相同牌面数字,且三张牌与两张牌不相同时,组合牌…...

【春秋云境】CVE-2022-28525
靶标介绍: ED01-CMS v20180505 存在任意文件上传漏洞 打开靶场: 盲猜一波弱密码admin:admin就进去了。登录后在图中位置点击进行图片更新,需要将密码等都写上 抓包将图片信息进行替换,并修改文件名: POST /admin…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...

Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...

沙箱虚拟化技术虚拟机容器之间的关系详解
问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西,但是如果把三者放在一起,它们之间到底什么关系?又有什么联系呢?我不是很明白!!! 就比如说: 沙箱&#…...

归并排序:分治思想的高效排序
目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法,由约翰冯诺伊曼在1945年提出。其核心思想包括: 分割(Divide):将待排序数组递归地分成两个子…...
Django RBAC项目后端实战 - 03 DRF权限控制实现
项目背景 在上一篇文章中,我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统,为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...