LeetCode: 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
。
示例 1:(图片转存自LeetCode)
输入:n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出:true
解释:存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2
- 0 → 2
示例 2:
输入:n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
输出:false
解释:不存在由顶点 0 到顶点 5 的路径.
提示:
1 <= n <= 2 * 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ui, vi <= n - 1
ui != vi
0 <= source, destination <= n - 1
- 不存在重复边
- 不存在指向顶点自身的边
class Solution {public boolean validPath(int n, int[][] edges, int source, int destination) {}
}
解题思路
- 将图的边列表(二维整数数组
edges
)转化为图的邻接表形式,以便快速访问每个节点的相邻节点信息。由于节点编号从0
到n-1
连续,故采用数组而非 HashMap 进行存储。 - 使用[[深度优先搜索]]递归地进行图的遍历。在遍历过程中,需要避免重复访问已经访问过的节点,因此使用一个
visited
数组来记录哪些节点已经被访问过。 - 终止条件:
- 如果在遍历过程中找到了
destination
,则可以立即返回true
,表示路径存在。 - 如果遍历了所有可能的路径都没有找到
destination
,则返回false
,表示路径不存在。
- 如果在遍历过程中找到了
代码示例
class Solution {public boolean validPath(int n, int[][] edges, int source, int destination) {// 如果起点和终点是同一个点,直接返回 trueif (source == destination) return true;// 构建邻接表,用数组表示图List<Integer>[] graph = new ArrayList[n];for (int i = 0; i < n; i ++) {graph[i] = new ArrayList<>();}// 填充邻接表for (int[] edge : edges) {int fromNode = edge[0];int toNode = edge[1];graph[fromNode].add(toNode);graph[toNode].add(fromNode);}// 创建访问标记数组boolean[] visited = new boolean[n];// 使用 DFS 检查是否存在从 source 到 destination 的路径return dfs(graph, visited, source, destination);}private boolean dfs(List<Integer>[] graph, boolean[] visited, int node, int destination) {// 如果当前节点是目标节点,返回 trueif (node == destination) return true;// 标记当前节点为已访问visited[node] = true;// 遍历所有相邻节点for (int neighbor : graph[node]) {// 如果相邻节点没有访问过,进行递归 DFSif (!visited[neighbor]) {if (dfs(graph, visited, neighbor, destination)) {// 找到能到达终点的路径就返回 truereturn true;}}}// 所有路径都不能到达终点,返回 falsereturn false;}
}
优化思路
这是一个经典的并查集问题。通过并查集的数据结构,可以高效地判断两个节点是否连通。每次将两个节点的根节点连接在一起,最终只需检查 source
和 destination
是否有相同的根节点即可。
优化后代码
class Solution {private int[] parent;private int[] rank; // 树的高度数组public boolean validPath(int n, int[][] edges, int source, int destination) {parent = new int[n];rank = new int[n];// 初始化并查集:每个节点的父节点为自己,rank 初始化为 1for (int i = 0; i < n; i++) {parent[i] = i;rank[i] = 1;}// 遍历所有边,将两个节点连接(即在并查集中合并)for (int[] edge : edges) {union(edge[0], edge[1]);}// 检查起始节点和目标节点是否在同一集合中return find(source) == find(destination);}// 查找某个节点的根节点,同时进行路径压缩private int find(int x) {if (parent[x] != x) { // 如果当前节点不是它自己的父节点,则继续向上查找parent[x] = find(parent[x]);}return parent[x];}// 合并两个集合,使用 rank 优化合并private void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {// 比较两个集合的 rank,rank 小的合并到大的上if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX; // 将 y 的根节点挂到 x 的根节点上} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY; // 将 x 的根节点挂到 y 的根节点上} else {parent[rootY] = rootX; // 如果 rank 相同,随意合并,但要增加新根的 rankrank[rootX]++;}}}
}
相关文章:

LeetCode: 1971. 寻找图中是否存在路径
寻找图中是否存在路径 原题 有一个具有 n 个顶点的 双向 图,其中每个顶点标记从 0 到 n - 1(包含 0 和 n - 1)。图中的边用一个二维整数数组 edges 表示,其中 edges[i] [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点…...
mysql 查询表所有数据,分页的语句
在 MySQL 中,若要从表中查询所有数据并实现分页,你可以使用 SELECT 语句结合 LIMIT 和 OFFSET 子句。LIMIT 用于指定返回的记录数,而 OFFSET 则用于指定从哪一条记录开始返回(即跳过的记录数)。 以下是一个基本的分页…...

TI DSP TMS320F280025 Note13:CPUtimer定时器原理分析与使用
TMS320F280025 CPUtimer定时器原理分析与使用 ` 文章目录 TMS320F280025 CPUtimer定时器原理分析与使用框图分析定时器中断定时器使用CPUtimers.cCPUtimers.h框图分析 定时器框图如图所示 定时器有一个预分频模块和一个定时/计数模块, 其中预分频模块包括一个 16 位的定时器分…...

Australis 相機率定軟體說明
概要 課堂中使用Australis這套軟體,順帶記錄操作過程 內容以老師口述及我測試的經過 照片為老師課堂提供之 說明 執行 Step1. 匯入照片 注意!!如果是Mac的作業系統,將資料夾移到Windows上的時候,建議創一個新的資料…...
C++入门(有C语言基础)
string类 string类初始化的方式大概有以下几种: string str1;string str2 "hello str2";string str3("hello str3");string str4(5, B);string str5[3] {"Xiaomi", "BYD", "XPeng"};string str6 str5[2];str…...

第四届高性能计算与通信工程国际学术会议(HPCCE 2024)
目录 大会简介 主办单位,承办单位 征稿主题 会议议程 参会方式 大会官网:www.hpcce.net 大会简介 第四届高性能计算与通信工程国际学术会议(HPCCE 2024)将于2024年11月22-24日在苏州召开。HPCCE 2024将围绕“高性能计算与通信工…...
负载均衡架构解说
负载均衡架构是一种设计模式,用于在多个服务器之间分配网络或应用流量,以提高资源利用率、最大化吞吐量、减少响应时间,并确保高可用性。 负载均衡架构的关键组件和概念: 关键组件 1.负载均衡器(Load Balancer&…...

【异常数据检测】孤立森林算法异常数据检测算法(数据可视化 Matlab语言)
摘要 本文研究了基于孤立森林算法的异常数据检测方法,并在MATLAB中实现了该算法的可视化。孤立森林是一种无监督的异常检测算法,主要通过构建决策树来区分正常数据和异常数据。本文使用真实数据集,通过二维可视化展示了检测结果。实验结果表…...

MKV转MP4丨FFmpeg的简单命令使用——视频格式转换
MKV是一种视频封装格式,很好用,也是OBS的默认推荐录制格式,因为不会突然断电关机而导致整个视频录制文件丢失。 但是MKV无法直接导入PR中剪辑,最直接的方法是将MKV转换为MP4格式,最方便且安全无损的转换方法便是用FFmp…...

git使用“保姆级”教程4——版本回退及分支讲解
一、版本回退 1、历史回退(版本回退)——命令行git reset --hard 版本编号 注意:当前命令会让工作区的内容发生改变,可以理解成历史区(master分支)直接回到工作区比如:从版本4回到版本3,则工作区只会显示版本3的代码内容 1.1、指…...
spring cache,Spring data redis
本项目使用Redis存储缓存数据,如何通过Java去访问Redis? 常用的有Jedis和Lettuce两个访问redis的客户端类库 ,Jedis和Lettuce都是redis提供的。其中Lettuce的性能和并发性要好一些,Spring Boot 默认使用的是 Lettuce 作为 Redis …...

10.数据结构与算法-线性表的应用(线性表与有序表的合并)
线性表的合并 有序表的合并 顺序表 链表...

GAN|对抗| 生成器更新|判别器更新过程
如上图所示,生成对抗网络存在上述内容: 真实数据集;生成器;生成器损失函数;判别器;判别器损失函数;生成器、判别器更新(生成器和判别器就是小偷和警察的关系,他们共用的…...
day01——登录功能
逻辑: 前端将登录信息通过报文的形式,发送给后端。后端进行登陆验证 2.1 根据接受的用户名,查询数据表。 若不存在该用户的记录,返回用户不存在。 若用户存在,判断数据库中的密码和接收的是否一致,不一致则…...

Flutter中使用FFI的方式链接C/C++的so库(harmonyos)
Flutter中使用FFI的方式链接C/C库(harmonyos) FFI plugin创建和so的配置FFI插件对so库的使用 FFI plugin创建和so的配置 首先我们可以根据下面的链接生成FFI plugin插件:开发FFI plugin插件 然后在主项目中pubspec.yaml 添加插件的依赖路径&…...
【C++】二义性
在C中,二义性(ambiguity)通常指的是编译器无法确定使用哪个函数、变量或类成员的情况。这种不确定性通常是由于继承和多态特性导致的。下面是一些常见的产生二义性的场景以及如何解决它们的方法: 1. 多重继承中的二义性 当一个类…...

高并发内存池(五):ThreadCache、CentralCache和PageCache的内存回收机制、阶段性代码展示和释放内存过程的调试
目录 ThreadCache的内存回收机制 补充内容1 补充内容2 补充内容3 补充内容4 ListTooLong函数的实现 CentralCache的内存回收机制 MapObjectToSpan函数的实现 ReleaseListToSpans函数的实现 PageCache的内存回收机制 补充内容1 补充内容2 ReleaseSpanToPageCache函…...
STL之stackqueue篇(上)探索C++ STL中的Queue与Stack——构建数据处理的基础框架
文章目录 前言一、stack1.1 定义与基本概念1.2 底层容器1.3 成员函数1.4 使用示例1.5 注意事项1.6 应用场景 二、queue2.1 定义与基本概念2.2 底层容器2.3 成员函数2.4 使用示例2.5 注意事项2.6 应用场景 前言 本文旨在深入探讨C STL中的queue与stack容器,从它们的…...
代码随想录算法训练营Day13
110.平衡二叉树 力扣题目链接:. - 力扣(LeetCode) 后序迭代 class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root)!-1;}public int getHeight(TreeNode root){if(rootnull){return 0;}int leftheightgetHei…...

基于STM32的智能门禁系统
目录 引言项目背景环境准备 硬件准备软件安装与配置系统设计 系统架构关键技术代码示例 RFID数据采集与处理门禁控制实现显示与报警功能应用场景结论 1. 引言 智能门禁系统在现代安防中占据重要地位,通常用于控制进入和离开特定区域的权限。通过基于STM32微控制器…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...