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

蓝桥杯-蓝桥幼儿园(并查集)

并查集的核心思想

并查集主要由两个操作构成:

  • Find:查找某个元素所在集合的根节点。并查集的特点是,每个元素都指向它自己的父节点,根节点的父节点指向它自己。查找过程中可以通过路径压缩来加速后续的查找操作,即将路径上所有节点直接指向根节点。

  • Union:将两个集合合并。如果两个元素属于不同的集合,我们将它们的集合合并起来。为了提高效率,我们可以使用按秩合并(将树较矮的集合合并到树较高的集合下)。

问题描述

在这里插入图片描述

思路分析

在这个问题中,我们可以将每个人视为一个节点,朋友关系视为连通关系,判断两个人是否是朋友其实就是判断他们是否属于同一组。通过并查集,我们可以高效地实现这两种操作:合并操作(Union)和查找操作(Find)。

  1. 查找操作:对于一个给定的节点,我们需要找到它的根节点,也就是它所在集合的代表元素。通过路径压缩的技巧,我们能够在查找过程中将路径上的所有节点直接指向根节点,从而减少后续查询的时间复杂度。

  2. 合并操作:当两个节点属于不同的集合时,我们需要将它们合并为一个集合。为了保证合并操作的效率,我们使用了按秩合并的策略,即将树矮的集合合并到树高的集合下,这样可以尽可能减少树的高度,提高查询效率。

解决步骤

  1. 初始化:首先我们创建一个大小为 n+1 的数组 parent,用于存储每个节点的父节点。在初始化时,每个节点的父节点都指向自己,表示每个节点是独立的。

  2. 操作解析

    • 对于 op == 1 的操作,表示将两个节点 xy 连接成一个集合。我们通过调用 union(x, y) 来合并它们的集合。
    • 对于 op == 2 的操作,表示查询两个节点 xy 是否属于同一集合。我们通过调用 find(x)find(y) 来查询它们的根节点,如果根节点相同,则表示它们是朋友关系。
  3. 路径压缩与按秩合并

    • find 操作中,我们使用了路径压缩技术。每次查找时,我们都将路径上的所有节点直接指向根节点,这样可以有效减少查找时的时间复杂度。
    • union 操作中,我们使用按秩合并的策略,通过比较两个集合的大小,将较小的集合合并到较大的集合中,从而保证了合并操作的效率。

代码:

import java.util.Scanner;// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {private static int[] parent;public static void main(String[] args) {//思想:维护一个数组将每个元素的朋友记录在里面,一个查找函数,一个合并函数Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();parent = new int[n + 1];// 初始化,每个节点的父节点指向自己for (int i = 1; i <= n; i++) {parent[i] = i;}for (int i = 0; i < m; i++) {int op = sc.nextInt();int x = sc.nextInt();int y = sc.nextInt();if (op == 1) {union(x, y);} else {System.out.println(find(x) == find(y) ? "YES" : "NO");}}}// 路径压缩的查找public static int find(int i) {// 我们需要找到该元素的根节点,先假设当前元素为根节点,//这个函数用来查找根节点,而根节点的父节点等于他自己,parent[root]=rootif (i != parent[i]) {parent[i] = find(parent[i]);}return parent[i];}// 合并优化public static void union(int x, int y) {//将两个元素的父节,若是不同则需统一,统一不需要,由我们自定义谁成为父节点,一直按照这个规矩下去int rootx = find(x);int rooty = find(y);//如果父节点不同就需要操作,相同就不需要if (rooty != rootx) {parent[rooty] = rootx;}}
}

相关文章:

蓝桥杯-蓝桥幼儿园(并查集)

并查集的核心思想 并查集主要由两个操作构成&#xff1a; Find&#xff1a;查找某个元素所在集合的根节点。并查集的特点是&#xff0c;每个元素都指向它自己的父节点&#xff0c;根节点的父节点指向它自己。查找过程中可以通过路径压缩来加速后续的查找操作&#xff0c;即将路…...

Ensemble of differential evolution variants(EDEV)

差分进化变体的集成1 在这项研究中&#xff0c;一个基于多种群的框架&#xff08;MPF&#xff09;被提议用于多个差分进化变体的集合。与PAP2不同&#xff0c;PAP通过时间预算分配策略和个体移民算子实现算法组合&#xff0c;MPF将整个种群划分为子种群&#xff0c;包括几个指…...

《AI开发工具和技能实战》第1集 Windows CMD 命令行操作指南:从基础到进阶

第1集 Windows CMD 命令行操作指南&#xff1a;从基础到进阶 在日常使用 Windows 系统时&#xff0c;命令提示符&#xff08;Command Prompt&#xff0c;简称 CMD&#xff09;是一个强大且灵活的工具。无论是文件管理、系统配置&#xff0c;还是网络诊断&#xff0c;CMD 都能提…...

实现一个拖拽排序组件:Vue 3 + TypeScript + Tailwind CSS

文章目录 一、项目背景与需求分析需求&#xff1a; 二、搭建基础项目1. 初始化 Vue 3 项目2. 安装 Tailwind CSS 三、设计拖拽排序组件1. 创建拖拽排序组件2. 说明&#xff1a; 四、完善样式与功能1. 样式调整2. 拖拽顺序更新 五、进一步优化与拓展1. 添加排序指示器2. 支持动态…...

哈希表(开散列)的实现

目录 引入 开散列的底层实现 哈希表的定义 哈希表的扩容 哈希表的插入 哈希表查找 哈希表的删除 引入 接上一篇&#xff0c;我们使用了闭散列的方法解决了哈希冲突&#xff0c;此篇文章将会使用开散列的方式解决哈希冲突&#xff0c;后面对unordered_set和unordered_map的…...

解决 Jetpack Compose 中 State 委托报错:“no method getValue“ 的终极指南

1. 必须的导入 ✅ import androidx.compose.runtime.getValue // 核心关键&#xff01;作用&#xff1a;为 State 类型添加 getValue() 操作符&#xff0c;使其支持 by 委托语法。为什么需要&#xff1a;Kotlin 的委托属性需要对象实现 getValue() 方法&#xff0c;Compose 通…...

我们如何思考AI创业投资

&#x1f3ac; Verdure陌矣&#xff1a;个人主页 &#x1f389; 个人专栏: 《C/C》 | 《转载or娱乐》 &#x1f33e; 种完麦子往南走&#xff0c; 感谢您的点赞、关注、评论、收藏、是对我最大的认可和支持&#xff01;❤️ 声明&#xff1a;本文作者转载&#xff0c;原文出自…...

1.ElasticSearch-入门基础操作

一、介绍 The Elastic Stack 包含ElasticSearch、Kibana、Beats、LogStash 这就是所说的ELK 能够安全可靠地获取任何来源、任何格式的数据&#xff0c;然后实时地对数据进行搜索、分析和可视化。Elaticsearch,简称为ES&#xff0c;ES是一个开源的高扩展的分布式全文搜索引擎,是…...

2.ElasticSearch-Java API

一、基础使用 1.1 Maven 坐标 <dependencies><dependency><groupId>org.elasticsearch</groupId><artifactId>elasticsearch</artifactId><version>7.8.0</version></dependency><!--es的客户端--><dependenc…...

蓝桥杯-小明的彩灯(差分)

问题描述&#xff1a; 差分数组 1. 什么是差分数组&#xff1f; 差分数组 c 是原数组 a 的“差值表示”&#xff0c;其定义如下&#xff1a; c[0] a[0]c[i] a[i] - a[i-1] &#xff08;i ≥ 1&#xff09; 差分数组记录了相邻元素的差值。例如&#xff0c;原数组 a [1, …...

vim定位有问题的脚本/插件的一般方法

在使用vim的过程中可能会遇到一些报错或其他不符合预期的情况&#xff0c;本文介绍一些我自己常用的定位有问题脚本/插件的方法&#xff08;以下方法同样适用于neovim&#xff09; 执行了某些命令的情况 这种情况最简单&#xff0c;使用:h 命令&#xff0c;如果插件有文档的话…...

EasyExcel实现图片导出功能(记录)

背景&#xff1a;在旧系统的基础上&#xff0c;导出一些工单信息时&#xff0c;现需要新添加处理人的签名或者签章&#xff0c;这就涉及图片的上传、下载、写入等几个操作。 1、EasyExcel工具类 &#xff08;1&#xff09;支持下拉框的导出。 import com.alibaba.excel.Easy…...

PCL拟合空间3D圆周 fit3DCircle

PCL版本 1.15.0 main.cpp #include<vector> #include<iostream> #include <array> #include <string> #include <windows.h> #include <omp.h> #include <charconv> // C17 #include <cstdlib> #include<chrono> #in…...

ansible 实现达梦7数据库初始化数据脚本写入

关于使用ansible 对ARM版达梦7的k8s自动化部署参考我的这篇操作 ansible-playbook 写arm版达梦7数据库的一键安装脚本-CSDN博客文章浏览阅读303次&#xff0c;点赞5次&#xff0c;收藏3次。达梦官方提供镜像目前是dm8_x86 版本&#xff0c;因为众所周知的国产化方面的需求&…...

leetcode每日刷题

Day18 Title45.jump(跳跃游戏 II) 解法一&#xff1a;动态规划 依然分三步走&#xff1a; 1.状态方程 2.dp[i]的意义 3.边界条件及初始值 优先思考第二个问题&#xff1a; dp[i]表示到达i时需要的最少跳数 第一个问题&#xff1a; dp[ij]min(dp[i]1,dp[ij]) 为什么&am…...

Ubuntu安装Nginx

Ubuntu安装Nginx 由于 Ubuntu 的 apt 命令内置了 nginx 源&#xff0c;因此不用配置 apt 就可以直接下载安装&#xff1a; apt install nginx -y查看 nginx 是否启动&#xff1a; ps -ef |grep nginx如果没有启动则需要手动启动&#xff1a; nginx1. 配置Nginx 使用浏览器…...

Hadoop的序列化

&#xff08;一&#xff09;什么是序列化与反序列化 序列化就是把内存中的对象&#xff0c;转换成字节序列&#xff08;或其他数据传输协议&#xff09;以便于存储到磁盘&#xff08;持久化&#xff09;和网络传输。 反序列化就是将收到字节序列&#xff08;或其他数据传输协议…...

拼多多商品详情接口爬虫实战指南

一、引言 在电商运营和数据分析中&#xff0c;获取商品详情数据是至关重要的一步。拼多多作为国内知名的社交电商平台&#xff0c;提供了丰富的商品详情接口&#xff0c;允许开发者通过API获取商品的详细信息。本文将详细介绍如何通过爬虫技术结合拼多多商品详情接口&#xff…...

python网络爬虫

一、Python爬虫核心库 HTTP请求库 requests&#xff1a;简单易用的HTTP请求库&#xff0c;处理GET/POST请求。aiohttp&#xff1a;异步HTTP客户端&#xff0c;适合高并发场景。 HTML/XML解析库 BeautifulSoup&#xff1a;基于DOM树的解析库&#xff0c;支持多种解析器&#xf…...

java线程安全-单例模式-线程通信

首先看看单例模式的写法 首先我们先来回顾一下饿汉式单例模式&#xff1a; class Singleton{private static Singleton singletonnew Singleton();private Singleton(){}public static Singleton getInstrance(){return singleton;} } public class Test{public static void …...

ASP.NET中将 PasswordHasher 使用的 PBKDF2 算法替换为更现代的 Scrypt 或 Argon2 算法

相关博文&#xff1a; .Net实现SCrypt Hash加密_scrypt加密-CSDN博客 密钥派生算法介绍 及 PBKDF2(过时)&#xff1c;Bcrypt(开始淘汰)&#xff1c;Scrypt&#xff1c; Argon2(含Argon2d、Argon2i、Argon2id)简介-CSDN博客 浅述.Net中的Hash算法&#xff08;顺带对称、非对称…...

力扣刷题-热题100题-第34题(c++、python)

23. 合并 K 个升序链表 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/merge-k-sorted-lists/?envTypestudy-plan-v2&envIdtop-100-liked 顺序合并 合并两个有序链表作为子函数&#xff0c;创建一个空链表&#xff0c;然后对含有多个链表的数组进…...

【SpringCloud】从入门到精通【上】

今天主播我把黑马新版微服务课程MQ高级之前的内容都看完了&#xff0c;虽然在看视频的时候也记了笔记&#xff0c;但是看完之后还是忘得差不多了&#xff0c;所以打算写一篇博客再温习一下内容。 课程坐标:黑马程序员SpringCloud微服务开发与实战 微服务 认识单体架构 单体架…...

如何给路由器配置代理IP?更改网络ip地址时出现错误怎么解决?

在现代网络环境中&#xff0c;无论是家庭用户还是企业用户&#xff0c;经常需要配置路由器以实现网络访问的灵活性和匿名性。其中&#xff0c;给路由器配置代理IP是一个常见的需求&#xff0c;尤其是在需要绕过地域限制、增强网络安全或进行匿名浏览时。然而&#xff0c;配置过…...

程序化广告行业(70/89):ABTester系统助力落地页优化实践

程序化广告行业&#xff08;70/89&#xff09;&#xff1a;ABTester系统助力落地页优化实践 在程序化广告领域摸爬滚打多年&#xff0c;深知持续学习和知识共享的重要性。写这篇博客&#xff0c;就是希望能和大家一起深入探索程序化广告行业&#xff0c;共同学习、共同进步。今…...

远程监控系统项目里练习

1、项目目标 设备端&#xff1a; &#xff08;1&#xff09;基于stm32mp157开发板&#xff0c;裁剪linux5.10.10&#xff0c;完成ov5640摄像头移植&#xff1b; &#xff08;2&#xff09;完成用户层程序&#xff0c;完成对摄像头的控制及与云端服务的数据交互。 云端&…...

Spring Boot 通过全局配置去除字符串类型参数的前后空格

1、问题 避免前端输入的字符串参数两端包含空格&#xff0c;通过统一处理的方式&#xff0c;trim掉空格 2、实现方式 /*** 去除字符串类型参数的前后空格* author yanlei* since 2022-06-14*/ Configuration AutoConfigureAfter(WebMvcAutoConfiguration.class) public clas…...

设计模式 --- 观察者模式

设计模式 --- 观察者模式 什么是观察者模式观察者模式典型应用 --- C#中的事件使用观察者模式实现事件处理机制 什么是观察者模式 观察者模式&#xff08;Observer Pattern&#xff09;是一种行为型设计模式&#xff0c;用于在对象之间建立一对多的依赖关系。当一个对象&#x…...

组播网络构建:IGMP、PIM 原理及应用实践

IP组播基础 组播基本架构 组播IP地址 一个组播IP地址并不是表示具体的某台主机&#xff0c;而是一组主机的集合&#xff0c;主机声明加入某组播组即标识自己需要接收目的地址为该组播地址的数据IP组播常见模型分为ASM模型和SSM模型ASM&#xff1a;成员接收任意源组播数据&…...

Java常见的23种设计模式

Java常见的23种设计模式 大家好&#xff0c;我是钢板兽&#xff01; 本文将系统梳理 Java 的设计模式&#xff0c;涵盖创建型、结构型和行为型三大类&#xff0c;结合定义、原理、优点、应用场景、示例代码&#xff0c;帮助你初步了解常见的23种设计模式。 一、设计模式分类…...

兔单B细胞单抗制备服务

1.兔单B细胞技术原理 兔单B细胞技术是近年来新发展的一类快速制备单克隆抗体的技术&#xff0c;是一种通过分离和单克隆化兔子体内的B细胞来制备单一来源的高特异性抗体的方法。基于流式细胞分选技术进行单B细胞单抗制备&#xff0c;利用每个B细胞只含有一个功能性重链可变区D…...

MySQL基础 [六] - 内置函数+复合查询+表的内连和外连

内置函数一般要用select调用 内置函数 日期函数 current_date函数 current_date函数用于获取当前的日期。如下&#xff1a; current_time函数 current_time函数用于获取当前的时间。如下&#xff1a; now函数 now函数用于获取当前的日期时间。如下&#xff1a; date函数 dat…...

nginx路径匹配的优先级

在 Nginx 配置中&#xff0c;当请求 /portal/agent/sse 时&#xff0c;会匹配 location ~* /sse$ 规则&#xff0c;而不是 location /portal。原因如下&#xff1a; 匹配规则解析 location ~* /sse$ ~* 表示 不区分大小写的正则匹配/sse$ 表示以 /sse 结尾的路径匹配结果&#…...

tcp/ip攻击及防范

作为高防工程师&#xff0c;我每天拦截数以万计的恶意流量&#xff0c;其中TCP/IP协议层攻击是最隐蔽、最具破坏性的威胁之一。常见的攻击手法包括&#xff1a; 1. SYN Flood攻击&#xff1a;攻击者发送大量伪造的SYN包&#xff0c;耗尽服务器连接资源&#xff0c;导致正常用…...

2025年3月中国电子学会青少年软件编程(Python)等级考试试卷(一级)答案 + 解析

更多真题在线练习系统&#xff1a;历年真题在线练习系统 一、单选题 1、下列哪个软件不能运行 Python 程序&#xff1f;&#xff08; &#xff09; A、JupyterNotebook B、Pycharm C、原版的Scratch D、IDLE 正确答案&#xff1a;C 答案解析&#xff1a;本题考察的 Pyt…...

TreeMap 核心知识点与面试题解析

TreeMap 核心知识点与面试题解析 一、TreeMap 基础概念 TreeMap 是 Java 集合框架中基于 红黑树&#xff08;Red-Black Tree&#xff09; 实现的 Map&#xff0c;具有以下特点&#xff1a; 有序性&#xff1a;默认按 key 的自然顺序&#xff08;Comparable&#xff09;或自定…...

深入理解 DevOps 与 CI/CD:概念、流程及优势

在当今快速发展的数字化时代,软件开发和交付的速度与质量成为企业在激烈竞争中脱颖而出的关键因素。DevOps 和 CI/CD 作为现代软件开发领域的重要理念和实践,正深刻地改变着软件开发生命周期的运作方式。本文将深入探讨 DevOps 的概念,详细解析 CI/CD 的内涵、管道阶段以及实…...

Flutter BloC 架构入门指南

BLoC (Business Logic Component) 是 Flutter 中一种流行的状态管理架构&#xff0c;它可以帮助你将业务逻辑与 UI 分离&#xff0c;使代码更清晰、可测试性更强。 核心概念 1. BloC 的核心组件 Events&#xff1a;用户交互或系统事件&#xff08;如按钮点击、网络请求完成&…...

OpenHarmony-AI调研

OpenHarmony-AI调研 文章目录 OpenHarmony-AI调研前言一、当前版本部署组件二、AI架构1.mindspore-lite2.ai_engine3.neural_network_runtime4.intelligent_voice_framework5.HDI驱动 三、应用1.命令行以及web运行deepseek-r12.与deepseek通过语音进行交互3.物品识别4.人脸识别…...

zk基础—zk实现分布式功能

1.zk实现数据发布订阅 (1)发布订阅系统一般有推模式和拉模式 推模式&#xff1a;服务端主动将更新的数据发送给所有订阅的客户端。 拉模式&#xff1a;客户端主动发起请求来获取最新数据(定时轮询拉取)。 (2)zk采用了推拉相结合来实现发布订阅 首先客户端需要向服务端注册自己关…...

Tips:用proxy解决前后端分离项目中的跨域问题

在前后端分离项目中&#xff0c;"跨域问题"是浏览器基于同源策略&#xff08;Same-Origin Policy&#xff09;对跨域请求的安全限制。当你的前端&#xff08;如运行在 http://localhost:3000 &#xff09;和后端&#xff08;如运行在 http://localhost:8080 &#…...

JMeterPlugins-Standard-1.4.0 插件详解:安装、功能与使用指南

JMeterPlugins-Standard-1.4.0 是 Apache JMeter&#xff08;一款流行的开源负载和性能测试工具&#xff09;的插件包&#xff0c;它扩展了 JMeter 的功能&#xff0c;提供了更多监听器&#xff08;Listeners&#xff09;、采样器&#xff08;Samplers&#xff09;和辅助组件&a…...

JMeter 中,Token 和 Cookie 的区别及实际应用

在 JMeter 中,Token 和 Cookie 都是用于处理用户会话和身份验证的机制,但它们的 工作原理、存储方式 和 应用场景 有显著区别。以下是详细对比和实际应用指南: 1. 核心区别 特性Token (如 JWT、OAuth)Cookie存储位置通常存储在 HTTP 请求头(如 Authorization: Bearer <t…...

蓝桥杯真题——好数、R格式

目录 蓝桥杯2024年第十五届省赛真题-好数 【模拟题】 题目描述 输入格式 输出格式 样例输入 样例输出 提示 代码1&#xff1a;有两个案例过不了&#xff0c;超时 蓝桥杯2024年第十五届省赛真题-R 格式 【vector容器的使用】 题目描述 输入格式 输出格式 样例输入…...

JavaScript惰性加载优化实例

这是之前的一位朋友的酒桌之谈&#xff0c;他之前负责的一个电商项目&#xff0c;刚刚开发万&#xff0c;首页加载时间特别长&#xff0c;体验很差&#xff0c;所以就开始排查&#xff0c;发现是在首页一次性加载所有js导致的问题&#xff0c;这个问题在自己学习的时候并不明显…...

0_Pytorch中的张量操作

[引言]张量的概念 1.基本概念 张量是一个通用的多维数组&#xff0c;可以表示标量&#xff08;0 维&#xff09;、向量&#xff08;1 维&#xff09;、矩阵&#xff08;2 维&#xff09;以及更高维度的数据。张量是 PyTorch 中的核心数据结构&#xff0c;用于表示和操作数据。…...

Java面试43-常见的限流算法有哪些?

限流算法是一种系统保护策略&#xff0c;主要是避免在流量高峰导致系统被压垮&#xff0c;造成系统不可用的问题。 常见的限流算法有五种&#xff1a; 计数器限流&#xff0c;一般用在单一维度的访问频率限制上&#xff0c;比如短信验证码每隔60s只能发送一次&#xff0c;或者…...

牛客网:树的高度 ← 根节点为 0 号节点

【题目来源】 https://www.nowcoder.com/questionTerminal/4faa2d4849fa4627aa6d32a2e50b5b25 【题目描述】 现在有一棵合法的二叉树&#xff0c;树的节点都是用数字表示&#xff0c;现在给定这棵树上所有的父子关系&#xff0c;求这棵树的高度。 【输入格式】 输入的第一行表…...

Linux:进程程序替换execl

目录 引言 1.单进程版程序替换 2.程序替换原理 3.6种替换函数介绍 3.1 函数返回值 3.2 命名理解 3.3 环境变量参数 引言 用fork创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支)&#xff0c;我们所创建的所有的子进程&#xff0c;执行的代码&#x…...

⑩数据中心M-LAG 实战

一、配置指导自己去看今天操作的是M-LAG 基础实验 二、配置代码信息回顾 ### 1、配置 M-LAG 系统 MAC 地址<H3C>system-view[H3C]m-lag system-mac ?H-H-H MAC address2a7a-53ee-0100 Bridge MAC address[H3C]m-lag system-mac### 2、配置 M-LAG 系统编号…...