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

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

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

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Redis数据倾斜问题解决

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

如何更改默认 Crontab 编辑器 ?

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

Rust 开发环境搭建

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

沙箱虚拟化技术虚拟机容器之间的关系详解

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

归并排序:分治思想的高效排序

目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法&#xff0c;由约翰冯诺伊曼在1945年提出。其核心思想包括&#xff1a; 分割(Divide)&#xff1a;将待排序数组递归地分成两个子…...

Django RBAC项目后端实战 - 03 DRF权限控制实现

项目背景 在上一篇文章中&#xff0c;我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统&#xff0c;为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...