当前位置: 首页 > 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微控制器…...

wordpress后台更新后 前端没变化的解决方法

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

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

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…...