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

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;
}

相关文章:

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

有一个具有 n 个顶点的 双向 图&#xff0c;其中每个顶点标记从 0 到 n - 1&#xff08;包含 0 和 n - 1&#xff09;。图中的边用一个二维整数数组 edges 表示&#xff0c;其中 edges[i] [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接&#x…...

FLINK SQL语法(1)

DDL Flink SQL DDL&#xff08;Data Definition Language&#xff09;是Flink SQL中用于定义和管理数据结构和数据库对象的语法。以下是对Flink SQL DDL的详细解析&#xff1a; 一、创建数据库&#xff08;CREATE DATABASE&#xff09; 语法&#xff1a;CREATE DATABASE [IF…...

【Fargo】1:基于libuv的udp收发程序

开发UDP处理程序 我正在开发一个基于libuv的UDP发送/接收程序,区分发送端和接收端,设计自定义包数据结构,识别和处理丢包和乱序。 创建项目需求 用户正在要求一个使用libuv的C++程序,涉及UDP发送和接收,数据包包括序列号和时间戳,接收端需要检测丢包和乱序包。 撰写代…...

WebSocket介绍和入门案例

目录 一、WebSocket 详解1. 定义与特点&#xff1a;2. 工作原理&#xff1a;3. 应用场景&#xff1a; 二、入门案例 一、WebSocket 详解 1. 定义与特点&#xff1a; WebSocket 是一种在单个 TCP 连接上进行全双工通信的协议。它允许客户端和服务器之间进行实时、双向的数据传…...

k8s集群版本升级

Kubernetes 集群版本升级是为了获得最新的功能、增强的安全性和性能改进。然而&#xff0c;升级过程需要谨慎进行&#xff0c;特别是在生产环境中。通常&#xff0c;Kubernetes 集群的版本升级应遵循逐步升级的策略&#xff0c;不建议直接跳过多个版本。 Kubernetes 版本升级的…...

XML 和 SimpleXML 简介

XML 和 SimpleXML 简介 XML&#xff08;可扩展标记语言&#xff09;是一种用于存储和传输数据的标记语言。它定义了一组规则&#xff0c;用于在文档中编码数据&#xff0c;以便人和机器都能理解。XML 的设计目标是既易于人类阅读&#xff0c;也易于机器解析。SimpleXML 是 PHP…...

MySQL 中 LIKE 语句的 `%` 和 `_` 以及 BLOB 和 TEXT 的详细解析和案例示范

1. LIKE 语句中的 % 和 _ 用法 1.1 % 通配符的用法 % 通配符代表零个或多个字符。它是 MySQL 中用于模糊匹配的强大工具之一&#xff0c;可以在任何字符的位置使用。 示例 1&#xff1a;查找以特定字符开头的记录 假设我们有一个电商订单系统的 orders 表&#xff0c;其中包…...

git clone卡在Receiving objects

git clone卡在Receiving objects 一直卡主 $ git clone gitxxx.git Cloning into xxx... remote: Enumerating objects: 75926, done. remote: Counting objects: 100% (18844/18844), done. remote: Compressing objects: 100% (6566/6566), done. Receiving objects: 60% (…...

vue+ant 弹窗可以拖动

通过自定义指令实现拖拽功能 在main.js里加入drag自定义指令 我自己测试时发现modal不管如何设置宽度&#xff0c;居中等&#xff0c;他的初始的left都为0&#xff0c;如果不设置好&#xff0c;容易出现点击后刚开始移动弹窗会偏移一段距离。 Vue.directive(drag, {bind(el)…...

(42)MATLAB中使用fftshift绘制以零为中心的功率谱

文章目录 前言一、MATLAB代码二、仿真结果画图 前言 在分析信号的频率分量时&#xff0c;将零频分量平移到频谱中心会很有帮助。本例给出绘制以零为中心的功率谱的方法。 一、MATLAB代码 代码如下&#xff1a; f 1; % 余弦波的振荡频率&#xf…...

Windows本地部署中文羊驼模型(Chinese-Alpaca-Pro-7B)(通俗易懂版)

最近由于项目原因需要部署大语言模型, 但碍于经济实力, 只能部署在笔记本电脑上部署量化模型, &#xff08;电脑至少有16G运行内存&#xff09;&#xff0c;搜集了网上的相关部署资料仍然踩了不少坑&#xff0c;原因在于开源项目在不断更新&#xff0c;导致我们看了别人的教程仍…...

Web3的挑战与机遇:技术发展的现状分析

在Web3的世界中&#xff0c;去中心化和用户主权的理念正逐渐走向主流&#xff0c;推动了现有商业模式和技术生态系统的深刻变革。区块链技术及其核心应用之一——智能合约&#xff0c;正在促使这一转变的发生。智能合约的主要功能是通过自动化和预设协议执行&#xff0c;以减少…...

LangGraph - Hierarchical Agent Teams

本文翻译整理自 Hierarchical Agent Teams https://langchain-ai.github.io/langgraph/tutorials/multi_agent/hierarchical_agent_teams/ 文章目录 一、前言二、设置三、创建工具四、Helper Utilities五、定义代理 Team研究 Team文档写作Team 六、添加图层 一、前言 在前面的…...

2021-04-14 proteus中仿真时74HC245三态双向端口扩展输出

缘由proteus中仿真时74HC245输出时电平显示灰色&#xff08;不确定电平状态&#xff09;是为什么&#xff1f;-编程语言-CSDN问答 缘由C语言翻译单片机开关检测器-编程语言-CSDN问答 参考74ls245的工作原理及作用详解 - 电子发烧友网 参考74ls245_百度百科...

解决UNSPSC商品分类的层级不足的方法

《联合国标准产品和服务守则》&#xff08;UNSPSC&#xff09;是一个分层框架&#xff0c;旨在对产品和服务进行分类。其主要目标是通过提供统一的方法来对产品和服务进行分类&#xff0c;从而简化采购和供应链管理。 虽然 UNSPSC 有效地将产品分为各种商品类别&#xff0c;但…...

Pytest基于fixture的参数化及解决乱码问题

我们知道&#xff0c;Pytest是Python技术栈下进行自动化测试的主流测试框架。支持灵活的测试发现、执行策略&#xff0c;强大的Fixture夹具和丰富的插件支持。 除了通过pytest的parametrize标签进行参数化外&#xff0c;我们通过fixture的param参数也可以比较方便地实现参数化…...

使用excel.js(layui-excel)进行layui多级表头导出,根据单元格内容设置背景颜色,并将导出函数添加到toolbar

本段是菜狗子的碎碎念&#xff0c;解决办法请直接从第二段开始看。layui多级表头的导出&#xff0c;弄了两天才搞定&#xff0c;中途一度想放弃&#xff0c;还好坚持下来了。一开始用的是layui的toolbar里自带的那个导出&#xff0c;但是多级表头没有正常导出&#xff0c;单元格…...

Mysql 5.7 安装与卸载(非常详细)

一、环境介绍 操作系统&#xff1a;CentOS 7 MySQL&#xff1a;5.7 二、MySQL卸载 # 查看软件 rpm -qa|grep mysql # 卸载MySQL yum remove -y mysql mysql-libs mysql-common rm -rf /var/lib/mysql rm /etc/my.cnf 继续查看是否还有 MySQL 软件&#xff0c;有的话继续删…...

030 elasticsearch查询、聚合

文章目录 查询聚合查询RestHighLevelClientElasticsearchRestTemplat SpringData对ES客户端的封装&#xff1a;ElasticsearchRestTemplate SpringData对CRUD的封装&#xff1a;ElasticsearchRepository 原生ES客户端&#xff1a;RestHighLevelClient 查询 package com.xd.cube…...

前端工程启动工具

一些思考 在公司项目中&#xff0c;需要启一个新的前端工程&#xff08;一个基于Webpack的React工程&#xff09;。因为同一个项目中有其他的前端工程&#xff0c;我们最开始想的是参考另外一个工程的配置重启一个新的工程&#xff0c;但是又因为原来的工程用的库版本都比较老…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...