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

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

寻找图中是否存在路径

原题

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

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

给你数组 edges 和整数 nsourcedestination,如果从 sourcedestination 存在 有效路径 ,则返回 true,否则返回 false

示例 1:(图片转存自LeetCode)

图片来源:LeetCode

输入:n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出:true
解释:存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2 
- 0 → 2

示例 2:

img

输入: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) {}
}

解题思路

  1. 将图的边列表(二维整数数组 edges)转化为图的邻接表形式,以便快速访问每个节点的相邻节点信息。由于节点编号从 0n-1 连续,故采用数组而非 HashMap 进行存储。
  2. 使用[[深度优先搜索]]递归地进行图的遍历。在遍历过程中,需要避免重复访问已经访问过的节点,因此使用一个 visited 数组来记录哪些节点已经被访问过。
  3. 终止条件:
    • 如果在遍历过程中找到了 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;}
}

优化思路

这是一个经典的并查集问题。通过并查集的数据结构,可以高效地判断两个节点是否连通。每次将两个节点的根节点连接在一起,最终只需检查 sourcedestination 是否有相同的根节点即可。

优化后代码

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 个顶点的 双向 图&#xff0c;其中每个顶点标记从 0 到 n - 1&#xff08;包含 0 和 n - 1&#xff09;。图中的边用一个二维整数数组 edges 表示&#xff0c;其中 edges[i] [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点…...

mysql 查询表所有数据,分页的语句

在 MySQL 中&#xff0c;若要从表中查询所有数据并实现分页&#xff0c;你可以使用 SELECT 语句结合 LIMIT 和 OFFSET 子句。LIMIT 用于指定返回的记录数&#xff0c;而 OFFSET 则用于指定从哪一条记录开始返回&#xff08;即跳过的记录数&#xff09;。 以下是一个基本的分页…...

TI DSP TMS320F280025 Note13:CPUtimer定时器原理分析与使用

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

Australis 相機率定軟體說明

概要 課堂中使用Australis這套軟體&#xff0c;順帶記錄操作過程 內容以老師口述及我測試的經過 照片為老師課堂提供之 說明 執行 Step1. 匯入照片 注意&#xff01;&#xff01;如果是Mac的作業系統&#xff0c;將資料夾移到Windows上的時候&#xff0c;建議創一個新的資料…...

C++入门(有C语言基础)

string类 string类初始化的方式大概有以下几种&#xff1a; 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)

目录 大会简介 主办单位&#xff0c;承办单位 征稿主题 会议议程 参会方式 大会官网&#xff1a;www.hpcce.net 大会简介 第四届高性能计算与通信工程国际学术会议&#xff08;HPCCE 2024&#xff09;将于2024年11月22-24日在苏州召开。HPCCE 2024将围绕“高性能计算与通信工…...

负载均衡架构解说

负载均衡架构是一种设计模式&#xff0c;用于在多个服务器之间分配网络或应用流量&#xff0c;以提高资源利用率、最大化吞吐量、减少响应时间&#xff0c;并确保高可用性。 负载均衡架构的关键组件和概念&#xff1a; 关键组件 1.负载均衡器&#xff08;Load Balancer&…...

【异常数据检测】孤立森林算法异常数据检测算法(数据可视化 Matlab语言)

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

MKV转MP4丨FFmpeg的简单命令使用——视频格式转换

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

git使用“保姆级”教程4——版本回退及分支讲解

一、版本回退 1、历史回退(版本回退)——命令行git reset --hard 版本编号 注意&#xff1a;当前命令会让工作区的内容发生改变&#xff0c;可以理解成历史区(master分支)直接回到工作区比如&#xff1a;从版本4回到版本3&#xff0c;则工作区只会显示版本3的代码内容 1.1、指…...

spring cache,Spring data redis

本项目使用Redis存储缓存数据&#xff0c;如何通过Java去访问Redis&#xff1f; 常用的有Jedis和Lettuce两个访问redis的客户端类库 &#xff0c;Jedis和Lettuce都是redis提供的。其中Lettuce的性能和并发性要好一些&#xff0c;Spring Boot 默认使用的是 Lettuce 作为 Redis …...

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

线性表的合并 有序表的合并 顺序表 链表...

GAN|对抗| 生成器更新|判别器更新过程

如上图所示&#xff0c;生成对抗网络存在上述内容&#xff1a; 真实数据集&#xff1b;生成器&#xff1b;生成器损失函数&#xff1b;判别器&#xff1b;判别器损失函数&#xff1b;生成器、判别器更新&#xff08;生成器和判别器就是小偷和警察的关系&#xff0c;他们共用的…...

day01——登录功能

逻辑&#xff1a; 前端将登录信息通过报文的形式&#xff0c;发送给后端。后端进行登陆验证 2.1 根据接受的用户名&#xff0c;查询数据表。 若不存在该用户的记录&#xff0c;返回用户不存在。 若用户存在&#xff0c;判断数据库中的密码和接收的是否一致&#xff0c;不一致则…...

Flutter中使用FFI的方式链接C/C++的so库(harmonyos)

Flutter中使用FFI的方式链接C/C库&#xff08;harmonyos&#xff09; FFI plugin创建和so的配置FFI插件对so库的使用 FFI plugin创建和so的配置 首先我们可以根据下面的链接生成FFI plugin插件&#xff1a;开发FFI plugin插件 然后在主项目中pubspec.yaml 添加插件的依赖路径&…...

【C++】二义性

在C中&#xff0c;二义性&#xff08;ambiguity&#xff09;通常指的是编译器无法确定使用哪个函数、变量或类成员的情况。这种不确定性通常是由于继承和多态特性导致的。下面是一些常见的产生二义性的场景以及如何解决它们的方法&#xff1a; 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容器&#xff0c;从它们的…...

代码随想录算法训练营Day13

110.平衡二叉树 力扣题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 后序迭代 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. 引言 智能门禁系统在现代安防中占据重要地位&#xff0c;通常用于控制进入和离开特定区域的权限。通过基于STM32微控制器…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...