Leetcode1971. 寻找图中是否存在路径
Every day a Leetcode
题目来源:1971. 寻找图中是否存在路径
解法1:并查集
并查集介绍:并查集详解
代码:
/** @lc app=leetcode.cn id=1971 lang=cpp** [1971] 寻找图中是否存在路径*/// @lc code=start
class UnionFind
{vector<int> father, size;public:UnionFind(int n) : father(n), size(n, 1){// iota函数可以把数组初始化为 0 到 n-1iota(father.begin(), father.end(), 0);}int find(int x){if (x == father[x])return x;elsereturn find(father[x]);}void connect(int p, int q){int fa_p = find(p), fa_q = find(q);if (fa_p != fa_q)father[fa_p] = fa_q;}bool isConnected(int p, int q){return find(p) == find(q);}
};class Solution
{
public:bool validPath(int n, vector<vector<int>> &edges, int source, int destination){UnionFind uf(n);for (vector<int> &edge : edges)uf.connect(edge[0], edge[1]);return uf.isConnected(source, destination);}
};
// @lc code=end
结果:

复杂度分析:
时间复杂度:O(n+m×α(m)),其中 n 是图中的顶点数,m 是图中边的数目,α 是反阿克曼函数。并查集的初始化需要 O(n) 的时间,然后遍历 m 条边并执行 m 次合并操作,最后对 source 和 destination 执行一次查询操作,查询与合并的单次操作时间复杂度是 O(α(m)),因此合并与查询的时间复杂度是 O(m×α(m)),总时间复杂度是 O(n+m×α(m))。
空间复杂度:O(n),其中 n 是图中的顶点数。并查集需要 O(n) 的空间。
解法2:深度优先搜索
首先从顶点 source 开始遍历并进行递归搜索。搜索时每次访问一个顶点 vertex 时,如果 vertex 等于 destination 则直接返回,否则将该顶点设为已访问,并递归访问与 vertex 相邻且未访问的顶点 next。如果通过 next 的路径可以访问到 destination,此时直接返回 true,当访问完所有的邻接节点仍然没有访问到 destination,此时返回 false。
代码:
class Solution
{
public:bool dfs(int source, int destination, vector<vector<int>> &adj, vector<bool> &visited){if (source == destination){return true;}visited[source] = true;for (int next : adj[source]){if (!visited[next] && dfs(next, destination, adj, visited)){return true;}}return false;}bool validPath(int n, vector<vector<int>> &edges, int source, int destination){vector<vector<int>> adj(n);for (auto &edge : edges){int x = edge[0], y = edge[1];adj[x].emplace_back(y);adj[y].emplace_back(x);}vector<bool> visited(n, false);return dfs(source, destination, adj, visited);}
};
结果:

复杂度分析:
时间复杂度:O(n+m),其中 n 表示图中顶点的数目,m 表示图中边的数目。
空间复杂度:O(n+m),其中 n 表示图中顶点的数目,m 表示图中边的数目。空间复杂度主要取决于邻接顶点列表、记录每个顶点访问状态的数组和递归调用栈,邻接顶点列表需要 O(m+n) 的存储空间,记录每个顶点访问状态的数组和递归调用栈分别需要 O(n) 的空间。
相关文章:
Leetcode1971. 寻找图中是否存在路径
Every day a Leetcode 题目来源:1971. 寻找图中是否存在路径 解法1:并查集 并查集介绍:并查集详解 代码: /** lc appleetcode.cn id1971 langcpp** [1971] 寻找图中是否存在路径*/// lc codestart class UnionFind {vector&…...
程序可以创建多少个用户界面对象?
有人提到这样一个问题:”一个程序最多可以注册多少个窗口类?” 问题的答案不是一个具体的数字。因为大多数用户界面对象都来自一个共享的内存池,我们称之为”桌面堆内存”。尽管我们可以计算一个最大的理论值,但是在实际的场景中࿰…...
业绩不俗,毛利率下滑,股价接连下跌,片仔癀将向何处去?
撰稿|行星 来源|贝多财经 10月16日,中药龙头企业漳州片仔癀药业股份有限公司(600436.SH,下称“片仔癀”)发布截至9月30日的2023年前三季度业绩报告。发布财报后,片仔癀的股价多日下跌。 10月17日、18日、19日和20日…...
云安全—docker容器镜像检测
0x00 前言 docker镜像是属于整个云原生的重要基石之一,如果从镜像开始就没有安全性的话,那么整个云原生也就没有任何的安全性可言。所以镜像检测技术就成为了一个比较重要的点,本篇将通过研究docker镜像工具来整体分析风险以及应对方案。 市…...
JDBC相关记录
JDBC:Java DadaBase Connectivity 即Java语言连接数据库。 本质:JDBC是SUN公司制定的一套接口(interface)。 作用:不同的数据库有自己独特设计原理,JDBC的可以让Java程序员关注业务本身,而不需要…...
Nginx的基本介绍 安装 配置文件 日志
一、Nginx介绍二、nginx的优点三、多路复用1、I/O multiplexing 多并发 四、nginx内部技术架构五、安装NginxNginx部署-yum安装获取Nginx的yum源yum安装Nginx浏览器访问 编译安装Nginx安装编译环境安装依赖环境创建nginx用户安装nginx启动nginx实现nginx开机自启(脚…...
docker部署nginx并设置挂载
前言: 最近在学习docker和nginx,因为容器在运行过程中,相关的配置文件及日志都会存在容器内。对容器以来较高,当容器不存在的时候。所有的文件也就都没有了。并且当需要查看日志,修改配置文件的时候必须进入到容器内部…...
MAC如何在根目录创建文件
在这之前先明确一下啥是根目录。 打开终端,输入cd /,然后输入 ls 查看根目录下有哪些文件 可以看到 usr、etc、opt 这些文件的地方才叫根目录,而不是以用户命名,可以看到音乐、应用程序、影片、桌面的地方哈 介绍一种叫做软连接…...
某全球领先的芯片供应商:优化数据跨网交换流程,提高安全管控能力
1、客户介绍 某全球领先的芯片供应商,成立于2005年,总部设于北京,在国内上海、深圳、合肥等地及国外多个国家和地区均设有分支机构和办事处,致力于为客户提供更优质、便捷的服务。 2、建设背景 该公司基于网络安全管理的需求&am…...
自然语言处理---文本预处理概述
自然语言处理(Natural Language Processing,简称NLP)是计算机科学与语言学中关注于计算机与人类语言间转换的领域。其主要应用于:语音助手、机器翻译、搜索引擎、智能问答等。 文本预处理概述 文本语料在输送给模型前一般需要一…...
GCC编译器 什么是宏? 标识符和关键字
一.GCC是什么? GCC是用于编译C语言和其它语言的开源软件。 全称是 GNU Compiler Collection,意思是GNU编译器集和。 支持多种操作系统和硬件平台。二.GCC的作用 GCC的作用是将源码转换为可执行的文件,使之可以在计算机上运行。三.GCC编译c文…...
【GESP】2023年06月图形化三级 -- 自幂数判断
文章目录 自幂数判断【题目描述】【输入描述】【输出描述】【参考答案】其他测试用例 自幂数判断 【题目描述】 自幂数是指N位数各位数字N次方之和是本身,如153是3位数,其每位数的3次方之和是153本身,因此153是自幂数,1634是4位数…...
MySQL常见面试题
一、存储引擎相关 (1)MySQL 支持哪些存储引擎? MySQL支持多种存储引擎,比如InnoDB,MyISAM, MySQL大于等于5.5之后,默认存储引擎是InnoDB (2)InnoDB 和 MyISAM 有什么区别? InnoD…...
前端HTML CSS JS风格规范
本文代码规范来自HTML/CSS代码开发规范文档 文件命名规范 使用小写字母、数字和下划线组成文件名。 避免使用特殊字符和空格。 使用语义化的命名,能够清晰地表达出文件的功能或内容。 目录结构规范 使用约定俗成的目录结构,如:src/compon…...
为什么spring默认采用单例bean
概 述 熟悉 Spring开发的朋友都知道 Spring 提供了 5种 scope,分别是: singleton: 单例模式,当spring创建applicationContext容器的时候,spring会欲初始化所有的该作用域实例,加上lazy-init就可以避免预处理…...
Redisson分布式锁学习
之前工作中一直使用redis来实现分布式锁,但是最近项目使用了云弹性,机器会涉及到扩缩容,涉及到优雅停机的问题,普通的redis分布锁,一般使用时会设置锁的时间,但是如果在加锁期间 JVM异常重启等发生会导致分…...
Metabase:简单快捷的商业智能与数据分析工具 | 开源日报 No.61
moby/moby Stars: 66.8k License: Apache-2.0 Moby 是一个由 Docker 创建的开源项目,旨在实现和加速软件容器化。它提供了工具包组件的“乐高集”,可以将它们组装成基于容器的自定义系统的框架。组件包括容器生成工具、容器注册表、业务流程工具、运行时…...
【无标题】高流量大并发Linux TCP性能调优
最近在使用jmeter做压测,当jmeter的并发量高的时候发现jmeter服务器一直报错Cannot assign requested address, 查看了一下发现系统中存在大量处于TIME_WAIT状态的tcp端口 netstat -n | awk ‘/^tcp/ {S[$NF]} END {for(a in S) print a, S[a]}’ TIME_W…...
优雅的用户体验:微信小程序中的多步骤表单引导
前言 在微信小程序中,实现一个多步骤表单引导界面既可以提供清晰的任务指引,又可以增加用户体验的互动性。本文将探讨如何使用微信小程序的特性,构建一个流程引导界面,帮助用户一步步完成复杂任务。我们将从设计布局和样式开始&am…...
Kotlin中的委托、属性委托和延迟加载
委托模式是一种常用的设计模式,用于将某个对象的责任委托给另一个对象来处理。在Kotlin中,委托可以通过关键字by来实现,主要分为类委托和属性委托两种形式。此外,Kotlin还提供了延迟加载的功能,可以在需要时才进行初始…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...
