当前位置: 首页 > 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…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...