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

算法学习笔记之并查集

news 来源：原创 2025/5/16 2:53:31

简介

问题描述：将编号为1-N的N个对象划分为不相交集合，在每个集合中，选择其中的某个元素代表所在集合。

常见两种操作：

1.合并两个集合

2.查找某元素属于哪个集合

实现方法1

用编号最小的元素标记所在集合；

定义一个数组Set[1...n]，其中Set[i]表示元素i所在的集合

效率分析1

查找：O(1)

find(x){return Set[x];}

合并：O(N)

 Merge(a, b){i = min(a, b);j = max(a, b);for(k = 1; k <= N; k++){if(Set[k] == j){Set[k] = i;}}}

实现方法2

效率分析2

查找：最坏为O(N)，一般为O(log N)

 find(x){r = x;while(Set[t] != r)r = Set[r];return r;}

合并：O(1)

 merge(a, b){Set[a] = b;}

最坏情况避免

例1

思路：并查集模板，计算集合数量即可

 #include<iostream>using namespace std;int bin[1002];int findx(int x){int r = x;while(bin[r] != r)r = bin[r];return r;}void merge(int x, int y){int fx, fy;fx = findx(x);fy = findx(y);if(fx != fy)bin[fx] = fy;}int main(){int n, m, x, y, count = -1;while(scanf("%d", &n), n){for(int i = 1; i <= n; i++){bin[i] = i;}for(scanf("%d", &m); m > 0; m--){scanf("%d %d", &x, &y);merge(x, y);}for(int i = 1; i <= n; i++){if(bin[i] == i){count ++;}}printf("%d\n", count);}return 0;}

例2

小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。

思路：判断迷宫是否有环

最小生成树

Kruskal算法

用于求最小生成树

理论基础：MST性质：对于一个连通图，至少存在一棵最小生成树，包含最短的这条边。

可以采用反证法进行证明

算法步骤：

一、把原始图的N个节点看成N个独立子图；

二、每次选取当前最短的边，若边的两端点属于不同的子图，则加入该边；否则放弃

三、循环操作步骤二，直到有N-1条边；

例3

分析：计算最小生成树

算法学习笔记之并查集

简介问题描述：将编号为1-N的N个对象划分为不相交集合，在每个集合中，选择其中的某个元素代表所在集合。常见两种操作： 1.合并两个集合 2.查找某元素属于哪个集合实现方法1 用编号最小的元素标记所在集合； 定义…...

编程日记 2025/5/16 2:53:31

【开源项目】ShowDoc适合IT团队的在线API文档、技术文档工具

1. 介绍通过showdoc，可以方便地使用markdown语法来书写出美观的API文档、数据字典文档、技术文档、在线excel文档等等。还可以利用showdoc的自动化能力，从程序注释中自动生成API文档，或者从搭配的RunApi客户端（类似postman的api…...

编程日记 2025/5/16 2:53:30

Tomcat添加到Windows系统服务中，服务名称带空格

要将Tomcat添加到Windows系统服务中，可以通过Tomcat安装目录中“\bin\service.bat”来完成，如果目录中没有service.bat，则需要使用其它方法。打到CMD命令行窗口，通过cd命令跳转到Tomcat安装目录的“\bin\”目录，然后执…...

编程日记 2025/5/16 2:46:56

SQL最佳实践（笔记）

写在前面： 之前baeldung的Java Weekly Reviews里面推荐了一篇关于SQL优化的文章，正好最近在学习数据库相关知识，记一些学习笔记原文地址：SQL Best Practices Every Java Engineer Must Know 1. 使用索引使用索引…...

编程日记 2025/5/11 9:06:22

历史性突破！DeepSeek双模型GitHub热度超OpenAI，展现中国AI力量

在2025年2月7日，中国AI领域传来了一则振奋人心的消息：DeepSeek旗下的两大开源项目在GitHub平台上实现了历史性突破，其Star数成功超越了OpenAI的明星项目。这一成就不仅标志着DeepSeek在技术研发和市场影响力上的重大飞跃，也为中国…...

编程日记 2025/5/13 4:38:27

deepseek+kimi一键生成PPT

1、deepseek生成大纲内容访问deepseek官方网站：https://www.deepseek.com/ 将你想要编写的PPT内容输入到对话框，点击【蓝色】发送按钮，让deepseek生成内容大纲，并以markdown形式输出。等待deepseek生成内容完毕后&#xff0c…...

编程日记 2025/5/14 1:59:33

Java学习

一、赋值赋值表达式，左边一定是变量，右边是变量或者数值，变量与数值都有类型，(数值里整数默认int,小数默认double) 类型由小转大，存储空间变大，数据不会丢失，是安全的，在需要时编译…...

编程日记 2025/5/14 7:32:55

Shell-基本命令与运算符

1.为什么要进行shell编程? 在Linux系统中，虽然有各种各样的图形化接口工具，但是shell仍然是一个非常灵活的工具。 Shell不仅仅是命令的收集，而且是一门非常棒的编程语言。您可以通过使用shell使大量的任务自动化， 因此&#…...

编程日记 2025/5/11 9:44:25

JUnit 5 自定义注解：方法级 JSON 参数注入

JUnit 5 自定义注解：方法级 JSON 参数注入为了实现在测试方法上使用注解，并通过注解属性指定参数名称和 JSON 字符串（转换为 Java 对象），以下是基于 JUnit 5 正确扩展接口的解决方案： 一、实现步骤 1. …...

编程日记 2025/5/15 17:48:46

一、系统版本 # cat /etc/anolis-release Anolis OS release 8.9 二、安装 # dnf install -y epel-release # wget -O /etc/yum.repos.d/jenkins.repo https://pkg.jenkins.io/redhat-stable/jenkins.repo # rpm --import https://pkg.jenkins.io/redhat-stable/jenkins.…...

编程日记 2025/5/13 22:36:35

【CXX】0 Rust与C 互操作利器：CXX库介绍与示例

CXX库是一个非常强大的工具，它使得Rust和C之间的互操作性变得既安全又高效。本专栏将展示如何使用CXX库来桥接Rust和C代码，同时保持两者语言的特性和惯用法。一、关键概念回顾类型安全：CXX库通过静态分析类型和函数签名来保护Rust和C的不…...

编程日记 2025/5/13 4:52:12

tensorflow环境中已安装库

1. 深度学习课前准备工作 Anaconda3、TensorFlow和keras安装方法 1 下载Anaconda： Anaconda3-5.2.0-Windows-x86_64.exe 双击安装，选定环境变量 2 开始菜单打开Anaconda Prompt：（2、3、4有链接科学上网） 创建环境&am…...

编程日记 2025/5/16 2:44:46

构建现代微服务安全体系：Spring Security、JWT 与 Spring Cloud Gateway 实践

构建现代微服务安全体系：Spring Security、JWT 与 Spring Cloud Gateway 实践本文将基于提供的代码示例，详细介绍如何在一个Java微服务项目中使用Spring Security、JWT和Spring Cloud Gateway来构建一个高效且安全的微服务体系，并整合性能优…...

编程日记 2025/5/12 13:41:49

蓝桥杯（B组）-每日一题（求最大公约数最小公倍数）

题目： 代码展现： #include<iostream> using namespace std; int main() {int m,n,x,y;cin>>m>>n;//输入两个整数int b;bm%n;//取余数xm;//赋值yn;while(b)//当余数不为0的时候{xy;//辗转相除求最小公约数yb;bx%y;}cout<<y<&…...

编程日记 2025/5/15 9:17:37

RocketMQ、RabbitMQ、Kafka 的底层实现、功能异同、应用场景及技术选型分析

1️⃣ 引言在现代分布式系统架构中，📩消息队列（MQ）是不可或缺的组件。它在系统🔗解耦、📉流量削峰、⏳异步处理等方面发挥着重要作用。目前，主流的消息队列系统包括 🚀RocketMQ、&…...

编程日记 2025/5/10 23:30:04

CEF132编译指南 MacOS 篇 - 构建 CEF (六)

1. 引言经过前面一系列的精心准备，我们已经完成了所有必要的环境配置和源码获取工作。本篇作为 CEF132 编译指南系列的第六篇，将详细介绍如何在 macOS 系统上构建 CEF132。通过配置正确的编译命令和参数，我们将完成 CEF 的构建工作&#xf…...

编程日记 2025/5/14 0:25:28

使用stm32控制esp01s

title: 使用stm32控制esp01s date: 2025年2月9日 18:41:20 tags: 单片机模块使用 categories: stm32 description: 使用stm32控制esp01s连接WiFi查看内容等操作前言使用stm32f103控制esp01s是步入物联网的第一步，接下来的文章会详细讲解如何使用stm32控制esp01s…...

编程日记 2025/5/9 22:31:54

返回倒数第N个链表节点

力扣题目：LCR 140. 训练计划 II - 力扣（LeetCode） 给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。示例 1： 输入：head [2,4,7,8], cnt 1 输…...

编程日记 2025/5/10 2:51:34

一、计算机等级考试——标准评分

（1）选择题未做选择题 （2）基本造作 （3）上网题 （4）文字题 （5）表格题 （6）演示文稿二、计算机等级考试——题库 （1&#x…...

编程日记 2025/5/13 7:46:11

tweenjs动画

目录编辑安装 HTML中应用 Threejs中应用安装 npm install tweenjs/tween.js HTML中应用 <script src"https://cdnjs.cloudflare.com/ajax/libs/tween.js/23.1.3/tween.umd.js"></script><div id"box"></div><style…...

编程日记 2025/5/14 17:33:33

IGBT工作原理

IGBT其实可以看成是BJT和MOS管的融合体，IGBT具有BJT的输入特性和mos管的输出特性。与 BJT 或 MOS管相比，绝缘栅双极型晶体管 IGBT 的优势在于它提供了比标准双极型晶体管更大的功率增益，以及更高的工作电压和更低的 MOS 管输入损耗。 IGBT是绝…...

编程日记 2025/5/15 0:47:03

FlashDecoding

Flash Attention是将Q划分到所有SM block上。每个SM block上的Q，负责和所有K和所有V进行计算，得到对应的结果。期间，SM block彼此之间，不需要通信。在prefill阶段，seqLength*batchSize*Heads足够多，所以每…...

编程日记 2025/5/14 13:53:12

03：Spring之Web

一：Spring整合web环境 1：web的三大组件 Servlet：核心组件，负责处理请求和生成响应。 Filter：用于请求和响应的预处理和后处理，增强功能。 Listener：用于监听 Web 应用中的事件，实…...

编程日记 2025/5/14 8:15:13

OpenWebUI使用DeepSeek R1满血版，DeepSeek R1 API调用

https://www.dong-blog.fun/post/1935 API调用登录这里： https://console.volcengine.com/ark/region:arkcn-beijing/endpoint?config%7B%7D 注册后，创建DeepSeek R1 API接入点： 接着Python就可以直接调用了： import os fro…...

编程日记 2025/5/11 22:40:46

DeepSeek模型场景应用：基于腾讯云HAI搭建IDEA开发助手

前言这段时间国产大模型DeepSeek十分火爆，DeepSeek模型凭借其强大的语言理解和生成能力，为开发场景带来了全新的可能性，DeepSeek模型场景应用也是十分广泛，而基于腾讯云HAI搭建IDEA开发助手，更是将这种潜力发挥到了极…...

编程日记 2025/5/13 8:13:14

HttpServletRequest 作用

HttpServletRequest 接口在 Java Servlet API 中扮演着至关重要的角色，它是 Servlet 处理客户端 HTTP 请求的核心对象。每次客户端（例如浏览器）向服务器发送一个 HTTP 请求时，Servlet 容器（例如 Tomcat）都…...

编程日记 2025/5/14 12:21:49

Python----PyQt开发（PyQt高级：手搓一个简单的记事本）

一、效果展示二、设计PyQt界面 2.1、设置图标 self.setWindowIcon(QIcon(./images/icon/1.png)) # 窗口图标 2.2、设置标题 self.file_name 无标题-新建文本文档 # 默认文件名 self.setWindowTitle(self.file_name) # 窗口标题 2.3、添加菜单栏、工具栏、状态栏 # 创…...

编程日记 2025/5/14 2:43:36

MySQL 索引失效案例：字符集不匹配的隐蔽影响

引言在 MySQL 数据库世界里，索引失效往往是性能问题的罪魁祸首。你是否曾遇到过这样的情况：明明加了索引，查询却慢如蜗牛？你是否曾以为小表查询就一定高效？本文将揭示一个真实的案例，一个容易被忽视的“隐…...

编程日记 2025/5/11 5:31:57

MySQL中类似PostgreSQL中的string_agg函数--GROUP_CONCAT函数的使用

文章目录结论：MySQL没有string_agg，但有GROUP_CONCATGROUP_CONCAT函数的基本用法示例注意事项系统变量 group_concat_max_len 如何查看和设置查看当前的group_concat_max_len值设置group_concat_max_len值相关源码相关链接结论：MySQL没有…...

编程日记 2025/5/13 6:24:32

科普：数据血缘理论中：任务血缘、表血缘、字段血缘

在讨论数据血缘时通常我们提到的是数据库血缘、数据表血缘和数据字段血缘，而“任务血缘”这一术语更多是在特定技术场景（如实时任务运维）中使用。数据血缘分类表血缘表血缘（或数据表血缘）是指数据在不同数据表之…...

编程日记 2025/5/13 15:03:38

凸性相关问题

内容大致上包括： 四边形不等式，决策单调性闵可夫斯基和优化 d p dp dpslope trick 优化 d p dp dp其他凸性相关问题决策单调性 1.1 一些约定对于 n m n\times m nm 的矩阵 A A A，定义： 子矩阵 A [ i 1 , . . . , i p …...

编程日记 2025/5/15 6:12:30

WPS计算机二级•文档的文本样式与编号

听说这是目录哦标题级别❤️新建文本样式快速套用格式🩷设置标题样式自定义设置多级编号🧡使用自动编号💛取消自动编号💚设置页面边框💙添加水印🩵排版技巧怎么分栏💜添加空白下划线&#x…...

编程日记 2025/5/14 5:51:05

开源堡垒机 JumpServer 社区版实战教程：一步步构建企业安全运维环境

文章目录开源堡垒机 JumpServer 社区版实战教程：一步步构建企业安全运维环境一、访问JumpServer1.1 登录1.2 功能模块1.3 系统设置1.3.1 基本设置1.3.2 邮件设置二、用户管理2.1 场景2.2 创建用户2.3 用户登录密码重置三、资产管理3.1 准备工作3.2 登录控制台3.3…...

编程日记 2025/5/11 11:31:05

二、数据类型、运算符

1. 数据的表示详解 1.1 算术运算符整数在计算机中的存储原理先从最基本的算术运算符开始学习，算术运算符有 - * / % ，其中*表示乘法，/表示除法，%表示取余数需要我们注意以下几点 /: 两个整数相除，结果也是一个…...

编程日记 2025/5/16 1:38:33

结构形模式---桥接模式

概念桥接模式是一种结构化模式，是将一个大类或者一系列的紧密相关的类拆分为抽象和现实两个独立部分的层次结构，通过引用独立层次对象的组合实现类。桥接模式可以将庞杂类拆分为几个类层次结构。此后， 你可以修改任意一个类层次结构而不…...

编程日记 2025/5/10 15:32:05

计算机网络知识速记：HTTP1.0和HTTP1.1

计算机网络知识速记：HTTP1.0和HTTP1.1 1. 基本概念 1.1 HTTP1.0 HTTP1.0是1996年发布的第一个正式版本，主要用于客户端与服务器之间的简单请求和响应交互。它的设计理念相对简单，适合处理一些基本的网页服务。 1.2 HTTP1.1 HTTP1.1是HTT…...

编程日记 2025/5/15 21:26:57

Windows下查看WIFI密码

目录命令行查看历史WIFI netsh wlan show profiles 命令行查看某一特定WIFI密码 netsh wlan show profile name “WIFI名” keyclear 打开命令行https://blog.csdn.net/weixin_70822378/article/details/145598560?spm1001.2014.3001.5502 命令行查看历史WIFI nets…...

编程日记 2025/5/15 21:48:26

Android车机DIY开发之软件篇(十二) AOSP12下载编译

Android车机DIY开发之软件篇(十二) AOSP12下载编译 sudo apt-get update sudo apt-get install git-core gnupg flex bison gperf build-essential zip curl zlib1g-dev gcc-multilib gmultilib libc6-dev-i386 lib32ncurses5-dev libx11-dev lib32z-dev ccache libgl1-mesa-…...

编程日记 2025/5/14 2:33:06

Datawhale Ollama教程笔记2

本期学习易错点： 改文件后缀改了models的存储地址后，把下载和新建的文件存储在什么地方注册hugging face,找到token. 学习手册：https://datawhalechina.github.io/handy-ollama/#/ 第 3 章自定义导入模型https://datawhalechina.gith…...

编程日记 2025/5/11 23:41:34

ClickHouse的前世今生

ClickHouse是一款由Yandex开发的高性能列式存储数据库管理系统，专为在线分析处理（OLAP）设计，适用于实时数据分析、大规模数据处理和复杂查询场景。以下是关于ClickHouse的安装、使用及应用场景的详细介绍：一、ClickHouse的安装 ClickHouse支持多种操作系统，包括Linux、…...

编程日记 2025/5/8 7:36:50

SSH隧道+Nginx：绿色通道详解（SSH Tunnel+nginx: Green Channel Detailed Explanation）

SSH隧道Nginx：内网资源访问的绿色通道问题背景模拟生产环境，使用两层Nginx做反向代理，请求公网IP来访问内网服务器的网站。通过ssh隧道反向代理来实现，重点分析一下nginx反代的基础配置。实验环境 1、启动内网服务器的tomca…...

编程日记 2025/5/7 8:34:11

html文件怎么转换成pdf文件，2025最新教程

将HTML文件转换成PDF文件，可以采取以下几种方法： 一、使用浏览器内置功能打开HTML文件：在Chrome、Firefox、IE等浏览器中打开需要转换的HTML文件。打印对话框：按下CtrlP（Windows）或CommandP（M…...

编程日记 2025/5/14 20:51:24

大促备战中稳定性建设策略与总结

文章目录接口流量评估、上下游依赖梳理降级能力建设应急响应预案建设压力测试监控报警建设容灾演练之前也专门写过日常稳定性建设的一些策略，传送门 -> 日常稳定性建设策略与总结，本文想专门聊聊大促期间做的一些稳定性保障，顺便记录自己…...

编程日记 2025/5/12 11:23:55

vscode/cursor+godot C#中使用socketIO

在 Visual Studio Code(VS Code)中安装 NuGet 包（例如SocketIOClient），你可以通过以下几种方法： 方法 1：使用dotnet cli 打开终端：在 VS Code 中按下Ctrl 或者通过菜单View -> Terminal打开终端。导…...

编程日记 2025/5/14 11:30:21

Uniapp 原生组件层级过高问题及解决方案

文章目录一、引言🏅二、问题描述📌三、问题原因❓四、解决方案💯4.1 使用 cover-view 和 cover-image4.2 使用 subNVue 子窗体4.3 动态隐藏原生组件4.4 使用 v-if 或 v-show 控制组件显示4.5 使用 position: fixed 布局五、总结&#x1f38…...

编程日记 2025/5/13 17:43:03

jQuery介绍（快速、简洁JavaScript库，诞生于2006年，主要目标是简化HTML文档操作、事件处理、动画和Ajax交互）

文章目录 **核心功能 & 亮点**1. **简化 DOM 操作**2. **链式调用**3. **跨浏览器兼容**4. **便捷的事件绑定**5. **Ajax 封装**6. **动画效果** **现状与适用场景**- **传统项目维护**：许多旧系统（如 WordPress 插件、老企业网站）仍依赖…...

编程日记 2025/5/12 13:04:25

第三节 docker基础之---Commit+Dockerfile制作

docker目前镜像的制作两种方法： 1，基于docker Commit制作镜像 2，基于dockerfile制作镜像，Dockerfile 为主流的制作方式如果不制作镜像删除容器之后则里面配置的文件也随之删除： [rootdocker ~]# docker images 查看…...

编程日记 2025/5/12 22:55:35

通过openresty和lua实现随机壁纸

效果： 图片存放路径： /home/jobs/webs/imgs/ ├── default/ │ ├── image1.jpg │ ├── image2.png ├── cats/ │ ├── cat1.jpg │ ├── cat2.gif ├── dogs/ │ ├── dog1.jpg访问http://demo.com/imgs/default 随机返回…...

编程日记 2025/5/15 4:57:53