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

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

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

给你数组 edges 和整数 nsource 和 destination,如果从 source 到 destination 存在 有效路径 ,则返回 true,否则返回 false 。

示例 1:

输入: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
  • 不存在重复边
  • 不存在指向顶点自身的边

代码:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
class Solution {
public: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];int y = edge[1];adj[x].push_back(y);adj[y].push_back(x);}queue<int> qu;qu.push(source);vector<bool> v(n, false);v[source] = true;while (!qu.empty()) {int ver = qu.front();qu.pop();if (ver == destination) {break;}for (auto next : adj[ver]) {if (!v[next]) {qu.push(next);v[next] = true;}}}return v[destination];}
};
int main() {int n; cin >> n;int col; cin >> col;vector<vector<int>> edges;edges.resize(n);for (auto i = 0; i < n; i++) {edges[i].resize(col);for (auto j = 0; j < col; j++) {cin >> edges[i][j];}}int source; cin >> source;int destination; cin >> destination;Solution solution = Solution();int res = solution.validPath(n, edges, source, destination);cout << res << endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/454515.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【贪心算法】刷刷刷刷刷刷题(上)

供自己复习&#xff0c;一篇10题左右 1.分发饼干2.分发糖果3.跳跃游戏I4.跳跃游戏II5.合并区间6.无重叠区间7.划分字母区间8.加油站 1.分发饼干 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&…

SERDES高速链路PCB设计的信号完整性考虑

链路包括一个发射模块、一个接收模块以及介于两者之间的所有称为“信道”的部分。在网络和电信设备中&#xff0c;信道通常包括线路卡和背板或中板。假设线性接收器处的波形只是发射波形与信道冲激响应的卷积&#xff0c;如果信道频率响应作为频率的函数是均匀的&#xff0c;则…

数据结构修炼——常见的排序算法:插入/希尔/选择/堆排/冒泡/快排/归并/计数

目录 一、常见的排序算法二、常见排序算法的实现2.1 排序算法回顾2.1.1 冒泡排序2.1.2 堆排序 2.2 直接插入排序2.3 希尔排序2.4 选择排序2.5 快速排序2.5.1 快速排序&#xff08;霍尔法&#xff09;2.5.2 快速排序&#xff08;挖坑法&#xff09;2.5.3 快速排序&#xff08;前…

GJB438C-2021《软件需求规格说明》的一处修订

今日偶见GJB438C-2021附录J《软件需求规格说明》的正文格式。 其中3.3.X.d条中的第2&#xff09;和5&#xff09;中使用了术语“数据元素组合体”&#xff1a; 在上一版本GJB438B-2009中的对应文字是&#xff1a; 我觉得把“包”改为“数据元素组合体”是合适的&#xff0c;其…

手机玩使命召唤21:黑色行动6?GameViewer远程玩使命召唤教程

使命召唤21&#xff1a;黑色行动 6这个第一人称射击游戏&#xff0c;将于10月25号上线&#xff01;如果你是使命召唤的老玩家&#xff0c;是不是也在期待这部新作&#xff1f;其实这个游戏不仅可以用电脑玩&#xff0c;还可以用手机玩&#xff0c;使用网易GameViewer远程就能让…

Termius工具在MAC的使用出现的问题:

Termius工具在MAC的使用出现的问题&#xff1a; 在使用SFTP时&#xff0c;出现不了本地的文件的位置 解决方案&#xff1a; 在Apple store下载的使用不了LOCAL SFTP&#xff0c; 需要在网页上进行下载才可以&#xff1a; 官网下载地址&#xff1a;https://termius.com/down…

Redis简介及其在NoSQL应用开发中的优化策略

Redis简介 REDIS数据库为NOSQL的其中一种&#xff0c;又称为REDIS缓存。 80%的系统瓶颈主要出现在数据库一侧 --(海量并发下&#xff0c;网络、磁盘IO开销会导致数据库性能出现瓶颈) --(海量数据下&#xff0c;数据查找可能需要关联上千张表、遍历数千万的数据、花费几分钟) 为…

python-django-mysql原生sql增删改查搭建搭建web项目

先看我本地的项目结构 1 设置虚拟环境 python -m venv venv .\venv\Scripts\activate 2 在虚拟环境中安装Django 执行 pip install -r requirements.txt asgiref3.8.1 backports.zoneinfo0.2.1 Django3.2 mysqlclient2.2.4 pytz2024.2 sqlparse0.5.1 typing-extensions4.1…

利用AI提升论文写作效率:高效提示词指南

利用AI提升论文写作效率&#xff1a;高效提示词指南 前言1. 论文构思与选题2. 文献综述3. 理论框架和方法论4. 数据分析与结果讨论5. 论文撰写与润色6. 参考文献与引用7. 摘要和关键词结语 前言 在这个信息爆炸的时代&#xff0c;学术研究和论文写作已经成为了知识传播和学术发…

微信小程序文字转语音播报案例

插件申请 在小程序官方申请同声传译插件&#xff0c;地址&#xff1a; mp.weixin.qq.com 引入插件 在app.json中加入 "plugins": {"WechatSI": {"version": "0.3.6","provider": "wx069ba97219f66d99"}},封装…

linux介绍与基本指令

前言 本次博客将会讲解linux的来源历史、linux操作系统的理解以及它的一些基本指令。 1.linux的介绍 linux的来源 linux的来源最初还是要说到unix操作系统的。 1968年&#xff0c;一些来自通用电器公司、贝尔实验室和麻省理工学院的研究人员开发了一个名叫Multics的特殊操作…

10.22 MySQL

存储过程 存储函数 存储函数是有返回值的存储过程&#xff0c;存储函数的参数只能是in类型的。具体语法如下&#xff1a; characteristic 特性 练习&#xff1a; 从1到n的累加 ​​​​​​ create function fun1(n int) returns int deterministic begindeclare total i…

数据结构与算法:贪心算法与应用场景

目录 11.1 贪心算法的原理 11.2 经典贪心问题 11.3 贪心算法在图中的应用 11.4 贪心算法的优化与扩展 总结 数据结构与算法&#xff1a;贪心算法与应用场景 贪心算法是一种通过选择当前最佳解来构造整体最优解的算法策略。贪心算法在很多实际问题中都取得了良好的效果&am…

MATLAB代码优化

MATLAB使用矩阵运算&#xff0c;因此使用矩阵运算速度要远超普通计算。 实验f(x,y)Asin(u0*xv0y)运算速度 代码&#xff1a; function [t, f, g] TASK(A, u0, v0, M, N) % M,N为像素点 tic for x 1:M %采用for循环计算for y 1:Nf(x, y) A * sin(u0 * (x-1) v0 * (y-1));…

ESP8266学习记录

一、接入点模式 NodeMCU可以建立WiFi网络供其它设备连接。当NodeMCU以此模式运行时&#xff0c;我们可以使用手机搜索NodeMCU所发出的WiFi网络并进行连接。 通过以下示例程序&#xff0c;NodeMCU将会建立一个名为我将点燃大海的WiFI。您可以使用手机或电脑连接该WiFi从而实现与…

图片无损放大工具Topaz Gigapixel AI v7.4.4 绿色版

Topaz A.I. Gigapixel是这款功能齐全的图象无损变大运用&#xff0c;应用可将智能机拍摄的图象也可以有着专业相机的高质量大尺寸作用。你可以完美地放大你的小照片并大规模打印&#xff0c;它根本不会粘贴。它具有清晰的效果和完美的品质。 借助AIGigapixel&#xff0c;您可以…

SD-WAN企业组网的应用场景

SD-WAN&#xff08;软件定义广域网&#xff09;能够实现企业不同站点之间的高效互联&#xff0c;确保分支机构、总部、数据中心以及云平台等站点的顺畅通信。本文将探讨从企业的WAN业务需求出发&#xff0c;可以将SD-WAN的组网场景分为哪几类。 SD-WAN的典型组网场景 企业站点之…

Java使用dom4j生成kml(xml)文件遇到No such namespace prefix: xxx is in scope on:问题解决

介绍addAttribute和addNamepsace: addAttribute 方法 addAttribute 方法用于给XML元素添加属性。属性&#xff08;Attributes&#xff09;是元素的修饰符&#xff0c;提供了关于元素的额外信息&#xff0c;并且位于元素的开始标签中。属性通常用于指定元素的行为或样式&#…

【华为HCIP实战课程十七】OSPF的4类及5类LSA详解,网络工程师

一、5类LSA详解 由ASBR产生,描述到AS外部的路由,通告到所有的区域(除了STUB区域和NSSA区域)。 我们在R6设备配置引入直连路由,R6的lo10 属于区域2 interface LoopBack10 ip address 6.6.6.6 255.255.255.255 ospf enable 1 area 0.0.0.2 [R6-ospf-1]import-route dire…

Java | Leetcode Java题解之第502题IPO

题目&#xff1a; 题解&#xff1a; class Solution {public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {int n profits.length;int curr 0;int[][] arr new int[n][2];for (int i 0; i < n; i) {arr[i][0] capital[i];arr[i][1] profi…