代码随想录(十二)——图论
并查集
并查集主要有三个功能。
- 寻找根节点,函数:find(int u),也就是判断这个节点的祖先节点是哪个
- 将两个节点接入到同一个集合,函数:join(int u, int v),将两个节点连在同一个根节点上
- 判断两个节点是否在同一个集合,函数:isSame(int u, int v),就是判断两个节点是不是同一个根节点
并查集可以解决的问题:两个节点是否在一个集合,也可以将两个节点添加到一个集合中。
难点在于根的路径压缩的理解

寻找图中是否存在路径
1971. 寻找图中是否存在路径
有一个具有 n 个顶点的 双向 图,其中每个顶点标记从 0 到 n - 1(包含 0 和 n - 1)。图中的边用一个二维整数数组 edges 表示,其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接,并且没有顶点存在与自身相连的边。
请你确定是否存在从顶点 source 开始,到顶点 destination 结束的 有效路径 。
给你数组 edges 和整数 n、source 和 destination,如果从 source 到 destination 存在 有效路径 ,则返回 true,否则返回 false 。
class Solution {
public:bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {/*深搜 / 广搜这里选择使用并查集进行实现使用并查集判断两个元素是否在同一个集合内部:step1: 使用join(u,v)把每条边加入到并查集step2: 使用 isSame(int u,int v) 判断是否是同一个根【即是否属于同一个集合】*/// step0: 并查集初始化init(n);// step1: 把每条边加入并查集for(vector<int> edge : edges) { // 每个元素就是一条边join(edge[0],edge[1]);}// step2: 使用 isSame(int u,int v) 判断是否是同一个根return isSame(source, destination);}
private:vector<int> father = vector<int>(200001,0) ; // 按照节点的大小定义数组长度void init(int n) { // 并查集初始化for(int i = 1; i <= n; i++) {father[i] = i; //初始化。每个元素都是自己的根}}// 并查集里寻找根的过程int find(int u) {return u== father[u] ? u : father[u] = find(father[u]);}// 判断 u 和 v 是否找到同一个根bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;}// 把 v-> u 这条边加入并查集 father[v] = uvoid join(int u, int v) {// 先判断两个元素是否在同一个集合内部u = find(u);v = find(v);if(u == v) return;father[v] = u;}
};
冗余连接
684. 冗余连接
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。
class Solution {public int[] findRedundantConnection(int[][] edges) {/**图论:删除相对于数来说的多余的一条边使用并查集的思想:把每条边都加入到其中,如果在加入的时候发现两个顶点已经同根;(即在一个并查集中)此时就说明这条边是一条冗余边,删除这条边即可*/int[] ans = null;init(edges.length);for(var edge : edges) {if(!join(edge[0],edge[1])) {ans = edge;break;}}return ans;}private int[] father;private void init(int vLen) { // 并查集的初始化 // 传入顶点数father = new int[vLen+1];for(int i=0; i < vLen; i++) {father[i] = i; // father[i] = i; 自身是自身的根,即刚开始所有节点都是单项的}}// 找到一个元素的根int find(int u) {return father[u] == u ? u: (father[u] = find(father[u]));}// 把 u->v 加入并查集private boolean join(int u, int v) {u = find(u);v = find(v);if(u == v) return false;father[u] = v;return true;}// 判断两个节点是否同根public boolean isSame(int u, int v) {u = find(u);v = find(v);return u == v;}
}
相关文章:
代码随想录(十二)——图论
并查集 并查集主要有三个功能。 寻找根节点,函数:find(int u),也就是判断这个节点的祖先节点是哪个将两个节点接入到同一个集合,函数:join(int u, int v),将两个节点连在同一个根节点上判断两个节点是否在…...
如何通过 Service Mesh 构建高效、安全的微服务系统
1. 引言 1.1.什么是 Service Mesh? Service Mesh 是一种基础架构层,负责处理微服务之间的通信,它通过在每个服务旁边部署代理(通常称为 Sidecar)来捕获和管理服务间的网络流量。这种方式解耦了微服务的业务逻辑和基础…...
MySQL 临时表详解
在 MySQL 中,临时表(Temporary Table)是一种非常有用的工具,可以帮助我们在执行复杂查询时存储临时数据。临时表的存在时间仅限于会话期,当会话结束后,临时表自动销毁。本文将详细讲解 MySQL 临时表的创建、…...
Kafka系列之:Kafka集群新增节点后实现数据均衡
Kafka系列之:Kafka集群新增节点后实现数据均衡 一、背景二、Kafka集群快速负载均衡方案三、按照Topic负载均衡Kafka系列之:使用Kafka Manager实现leader分区平衡和broker节点上分区平衡一、背景 Kafka集群新增节点,要使得每个节点数据均衡,在增加完kafka topic分区后,要进…...
实验:使用Oxygen发布大型手册到Word格式
此前,我曾发表过一篇文章《结构化文档发布的故事和性能调优》,文中讨论了在将大型DITA手册转换为PDF格式时可能遇到的性能挑战及相应的优化策略。 近日,有朋友咨询,若将同样的大型手册输出为MS Word格式,是否也会面临…...
一个基于.NET8+WPF开源的简单的工作流系统
项目介绍 AIStudio.Wpf.AClient 是一个基于 WPF (Windows Presentation Foundation) 构建的客户端框架,专为开发企业级应用而设计。该项目目前版本为 6.0,进行了全面优化和升级,提供了丰富的功能和模块,以满足不同场景下的开发需…...
MFC工控项目实例二十七添加产品参数
承接专栏《MFC工控项目实例二十六创建数据库》 在型号参数界面添加三个参数试验时间、最小值、最大值。变量为double m_edit_time; double m_edit_min; double m_edit_max; 1、在SEAL_PRESSURE.h中添加代码 class CProductPara { public:union{struct{...double m_edit_min;…...
PgSQL常用SQL语句
PgSQL常用SQL语句 这是我在这个网站整理的笔记,有错误的地方请指出,关注我,接下来还会持续更新。 作者:神的孩子都在歌唱 PgSQL是一种开源的关系型数据库管理系统,它是PostgreSQL的一种实现。本文将介绍一些常用的PgSQL SQL语句&a…...
python多线程处理xlsx,多进程访问接口
import pandas as pd from concurrent.futures import ThreadPoolExecutor# 读取Excel文件 file_path scence.xlsx df pd.read_excel(file_path)# 定义每10行处理逻辑 def process_rows(start_idx):end_idx min(start_idx 10, len(df)) # 处理每10行for i in range(start_…...
PDF无法转换成其他格式的常见原因与解决方法解析
在处理PDF文件转换时,用户常常会遇到一些问题,导致无法将PDF转换为其他格式(如Word、Excel、或图片等)。以下是一些常见原因以及解决方法的解析。 ## 一、常见原因 ### 1. **PDF文件的安全性设置** 许多PDF文件在创建时可能设置…...
蓝桥杯第二十场小白入门赛
2.黛玉泡茶 我的思路代码:(但我不知道哪有错误) #include<iostream> #include<vector> #include<algorithm> using namespace std;int main(){int n,m,k,res1;cin>>n>>m>>k;vector<int>num(n1,0…...
K 个一组反转链表
力扣第 25 题:K 个一组反转链表 题目描述 给定一个链表,将链表每k个节点一组进行反转,并返回修改后的链表。如果最后一组节点数少于 k,则保持原顺序。 示例 1: 输入:1 -> 2 -> 3 -> 4 -> 5&…...
#深度学习:从基础到实践
深度学习是人工智能领域近年来最为火热的技术之一。它通过构建由多个隐藏层组成的神经网络模型,能够从海量数据中自动学习特征和表征,在图像识别、自然语言处理、语音识别等领域取得了突破性进展。本文将全面介绍深度学习的基础知识、主要算法和实践应用,帮助您快速…...
Android Kotlin中协程详解
博主前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住也分享一下给大家, 👉点击跳转到教程 前言 Kotlin协程介绍: Kotlin 协程是 Kotlin 语言中的一种用于处理异步编程的机制。它提供了一…...
【webpack学习】
webpack由于历史包袱导致复杂,只要把握关键流程即可 webpack的主要流程loader plugin难点:HMR / 懒加载 原理webpack 的优化手段 构建工具对比 webpack :可以打包任何资源,配置略复杂,适合项目开发rollup࿱…...
H5实现PDF文件预览,使用pdf.js-dist进行加载
H5实现PDF文件预览,使用pdf.js-dist进行加载 一、应用场景 在H5平台上预览PDF文件是在原本已经开发完成的系统中新提出的需求,原来的系统业务部门是在PC端进行PDF的预览与展示,但是现在设备进行了切换,改成了安卓一体机进行文件…...
面试域——面试系统工程
摘要 1. 当前就业面试场景 1.1. 招聘市场的“551 定律” 你知道招聘市场的“551 定律”吗? 551 定律:每一层筛选环节都会有百分之十的折损率。一个岗位从接收简历到发下 Offer 至少要筛选 500 份左右的简历、面试 50 人左右、只有 5 人左右通过面试&am…...
PHP-FPM 性能配置优化
4 核 8 G 服务器大约可以开启 500 个 PHP-FPM,极限吞吐量在 580 qps (Query Per Second 每秒查询数)左右。 Nginx php-fpm 是怎么工作的? php-fpm 全称是 PHP FastCGI Process Manager 的简称,从名字可得知ÿ…...
渗透测试-百日筑基—SQL注入篇时间注入绕过HTTP数据编码绕过—下
day8-渗透测试sql注入篇&时间注入&绕过&HTTP数据编码绕过 一、时间注入 SQL注入时间注入(也称为延时注入)是SQL注入攻击的一种特殊形式,它属于盲注(Blind SQL Injection)的一种。在盲注中,攻击…...
Unity - UGUI动静分离
原理:UGUI 是基于Canvas来进行合并计算的 1.不同Cavans的UI元素,是无法合批渲染,无法实现同一个drawcall 2. 每次合批的时候,会合并计算Canvas下所有的UI元素 , 具体流程: Step1: 对Cavans下所有的UI元素进行合批计算 Step2: …...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
