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

代码随想录(十二)——图论

并查集

并查集主要有三个功能。

  1. 寻找根节点,函数:find(int u),也就是判断这个节点的祖先节点是哪个
  2. 将两个节点接入到同一个集合,函数:join(int u, int v),将两个节点连在同一个根节点上
  3. 判断两个节点是否在同一个集合,函数:isSame(int u, int v),就是判断两个节点是不是同一个根节点

并查集可以解决的问题:两个节点是否在一个集合,也可以将两个节点添加到一个集合中。

难点在于根的路径压缩的理解

寻找图中是否存在路径 

1971. 寻找图中是否存在路径

有一个具有 n 个顶点的 双向 图,其中每个顶点标记从 0 到 n - 1(包含 0 和 n - 1)。图中的边用一个二维整数数组 edges 表示,其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接,并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始,到顶点 destination 结束的 有效路径 。

给你数组 edges 和整数 nsource 和 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;}
}

相关文章:

代码随想录(十二)——图论

并查集 并查集主要有三个功能。 寻找根节点&#xff0c;函数&#xff1a;find(int u)&#xff0c;也就是判断这个节点的祖先节点是哪个将两个节点接入到同一个集合&#xff0c;函数&#xff1a;join(int u, int v)&#xff0c;将两个节点连在同一个根节点上判断两个节点是否在…...

如何通过 Service Mesh 构建高效、安全的微服务系统

1. 引言 1.1.什么是 Service Mesh&#xff1f; Service Mesh 是一种基础架构层&#xff0c;负责处理微服务之间的通信&#xff0c;它通过在每个服务旁边部署代理&#xff08;通常称为 Sidecar&#xff09;来捕获和管理服务间的网络流量。这种方式解耦了微服务的业务逻辑和基础…...

MySQL 临时表详解

在 MySQL 中&#xff0c;临时表&#xff08;Temporary Table&#xff09;是一种非常有用的工具&#xff0c;可以帮助我们在执行复杂查询时存储临时数据。临时表的存在时间仅限于会话期&#xff0c;当会话结束后&#xff0c;临时表自动销毁。本文将详细讲解 MySQL 临时表的创建、…...

Kafka系列之:Kafka集群新增节点后实现数据均衡

Kafka系列之:Kafka集群新增节点后实现数据均衡 一、背景二、Kafka集群快速负载均衡方案三、按照Topic负载均衡Kafka系列之:使用Kafka Manager实现leader分区平衡和broker节点上分区平衡一、背景 Kafka集群新增节点,要使得每个节点数据均衡,在增加完kafka topic分区后,要进…...

实验:使用Oxygen发布大型手册到Word格式

此前&#xff0c;我曾发表过一篇文章《结构化文档发布的故事和性能调优》&#xff0c;文中讨论了在将大型DITA手册转换为PDF格式时可能遇到的性能挑战及相应的优化策略。 近日&#xff0c;有朋友咨询&#xff0c;若将同样的大型手册输出为MS Word格式&#xff0c;是否也会面临…...

一个基于.NET8+WPF开源的简单的工作流系统

项目介绍 AIStudio.Wpf.AClient 是一个基于 WPF (Windows Presentation Foundation) 构建的客户端框架&#xff0c;专为开发企业级应用而设计。该项目目前版本为 6.0&#xff0c;进行了全面优化和升级&#xff0c;提供了丰富的功能和模块&#xff0c;以满足不同场景下的开发需…...

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语句 这是我在这个网站整理的笔记,有错误的地方请指出&#xff0c;关注我&#xff0c;接下来还会持续更新。 作者&#xff1a;神的孩子都在歌唱 PgSQL是一种开源的关系型数据库管理系统&#xff0c;它是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文件转换时&#xff0c;用户常常会遇到一些问题&#xff0c;导致无法将PDF转换为其他格式&#xff08;如Word、Excel、或图片等&#xff09;。以下是一些常见原因以及解决方法的解析。 ## 一、常见原因 ### 1. **PDF文件的安全性设置** 许多PDF文件在创建时可能设置…...

蓝桥杯第二十场小白入门赛

2.黛玉泡茶 我的思路代码&#xff1a;&#xff08;但我不知道哪有错误&#xff09; #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 题&#xff1a;K 个一组反转链表 题目描述 给定一个链表&#xff0c;将链表每k个节点一组进行反转&#xff0c;并返回修改后的链表。如果最后一组节点数少于 k&#xff0c;则保持原顺序。 示例 1&#xff1a; 输入&#xff1a;1 -> 2 -> 3 -> 4 -> 5&…...

#深度学习:从基础到实践

深度学习是人工智能领域近年来最为火热的技术之一。它通过构建由多个隐藏层组成的神经网络模型&#xff0c;能够从海量数据中自动学习特征和表征,在图像识别、自然语言处理、语音识别等领域取得了突破性进展。本文将全面介绍深度学习的基础知识、主要算法和实践应用,帮助您快速…...

Android Kotlin中协程详解

博主前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住也分享一下给大家&#xff0c; &#x1f449;点击跳转到教程 前言 Kotlin协程介绍&#xff1a; Kotlin 协程是 Kotlin 语言中的一种用于处理异步编程的机制。它提供了一…...

【webpack学习】

webpack由于历史包袱导致复杂&#xff0c;只要把握关键流程即可 webpack的主要流程loader plugin难点&#xff1a;HMR / 懒加载 原理webpack 的优化手段 构建工具对比 webpack &#xff1a;可以打包任何资源&#xff0c;配置略复杂&#xff0c;适合项目开发rollup&#xff1…...

H5实现PDF文件预览,使用pdf.js-dist进行加载

H5实现PDF文件预览&#xff0c;使用pdf.js-dist进行加载 一、应用场景 在H5平台上预览PDF文件是在原本已经开发完成的系统中新提出的需求&#xff0c;原来的系统业务部门是在PC端进行PDF的预览与展示&#xff0c;但是现在设备进行了切换&#xff0c;改成了安卓一体机进行文件…...

面试域——面试系统工程

摘要 1. 当前就业面试场景 1.1. 招聘市场的“551 定律” 你知道招聘市场的“551 定律”吗&#xff1f; 551 定律&#xff1a;每一层筛选环节都会有百分之十的折损率。一个岗位从接收简历到发下 Offer 至少要筛选 500 份左右的简历、面试 50 人左右、只有 5 人左右通过面试&am…...

PHP-FPM 性能配置优化

4 核 8 G 服务器大约可以开启 500 个 PHP-FPM&#xff0c;极限吞吐量在 580 qps &#xff08;Query Per Second 每秒查询数&#xff09;左右。 Nginx php-fpm 是怎么工作的&#xff1f; php-fpm 全称是 PHP FastCGI Process Manager 的简称&#xff0c;从名字可得知&#xff…...

渗透测试-百日筑基—SQL注入篇时间注入绕过HTTP数据编码绕过—下

day8-渗透测试sql注入篇&时间注入&绕过&HTTP数据编码绕过 一、时间注入 SQL注入时间注入&#xff08;也称为延时注入&#xff09;是SQL注入攻击的一种特殊形式&#xff0c;它属于盲注&#xff08;Blind SQL Injection&#xff09;的一种。在盲注中&#xff0c;攻击…...

Unity - UGUI动静分离

原理&#xff1a;UGUI 是基于Canvas来进行合并计算的 1.不同Cavans的UI元素&#xff0c;是无法合批渲染&#xff0c;无法实现同一个drawcall 2. 每次合批的时候&#xff0c;会合并计算Canvas下所有的UI元素 , 具体流程: Step1: 对Cavans下所有的UI元素进行合批计算 Step2: …...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...