代码随想录算法训练营第55天 | 寻找存在的路径

寻找存在的路径 

题目描述

给定一个包含 n 个节点的无向图中,节点编号从 1 到 n (含 1 和 n )。

你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。

输入描述

第一行包含两个正整数 N 和 M,N 代表节点的个数,M 代表边的个数。 

后续 M 行,每行两个正整数 s 和 t,代表从节点 s 与节点 t 之间有一条边。 

最后一行包含两个正整数,代表起始节点 source 和目标节点 destination。

输出描述

输出一个整数,代表是否存在从节点 source 到节点 destination 的路径。如果存在,输出 1;否则,输出 0。

输入示例

5 4
1 2
1 3
2 4
3 4
1 4

输出示例

1

提示信息

数据范围:

1 <= M, N <= 100。

思路:这道题涉及到了并查集的概念。

那么什么是并查集呢,简单来说并查集的功能就是能够判断两个节点是否在同一个集合里面,并且还能够将两个节点加入同一个集合里面。

实现的方式呢就是使用一个parent数组来保存节点之间的联系,就好像一棵二叉树一样,结点之间是有联系的。

所以一般模板涉及到四个函数,init函数负责初始化每个结点的根节点为自身;find函数负责找到每个结点的根,这里涉及到了路径压缩,也就是可能某个结点距离它的根很远,但是在最后递归找到后,直接将根的值返回,保存在了该结点的parent里面,这样就将路径压缩短了;isSame函数则是判断两个结点的根是否相等;join函数则是将两个结点加入同一个并查集中。

正是因为有了路径压缩,所以一般来说,并查集的时间复杂度是O(logn)到O(1)之间的,刚开始可能是O(logn),但是随着规模越来越大,路径不断被压缩,最终查找的效率就会趋近于O(1)。

所以说回到这道题本身,判断是否有从source到destination的可达路径,那么就将所有边join后,判断source与destination是否具有相同的根即可。如果是,说明是存在这样的一条可达路径;如果不是,则不存在这样一条可达的路径

#include<iostream>
#include<vector>
using namespace std;int n, m;
vector<int> parent(101);
void init(){for(int i = 1; i <= n; i ++){parent[i] = i;//初始化}
}
//找寻根节点
int find(int u){return u == parent[u] ? u : parent[u] = find(parent[u]);//压缩路径
}
//判断两个节点的根节点是否相等
bool isSame(int u, int v){u = find(u);v = find(v);return u == v;
}//存在v->u这样一条边
//将边的两个节点加入并查集
void join(int u, int v){u = find(u);v = find(v);if(u == v) return;parent[v] = u;
}int main(){while(cin >> n >> m){init();int node1, node2, source, destination;for(int i = 0; i < m; i ++){cin >> node1 >> node2;join(node1, node2);}cin >> source >> destination;if(isSame(source, destination)) cout << 1 << endl;else cout << 0 << endl;}
}

感谢你的阅读,希望我的文章能够给你帮助,如果有帮助,麻烦点赞加收藏,或者点点关注,非常感谢。

如果有什么问题欢迎评论区讨论!

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

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

相关文章

音视频入门基础:AAC专题(9)——FFmpeg源码中计算AAC裸流每个packet的duration和duration_time的实现

音视频入门基础&#xff1a;AAC专题系列文章&#xff1a; 音视频入门基础&#xff1a;AAC专题&#xff08;1&#xff09;——AAC官方文档下载 音视频入门基础&#xff1a;AAC专题&#xff08;2&#xff09;——使用FFmpeg命令生成AAC裸流文件 音视频入门基础&#xff1a;AAC…

极度精简 Winows11 系统镜像!Tiny11 2311下载 - 支持苹果 M 芯片 Mac 安装 (ARM 精简版)!

最新推出的 Tiny11 是一款极端精简版 Windows 11 系统镜像&#xff0c;针对苹果 M 芯片 Mac 用户&#xff08;ARM 架构&#xff09;提供良好支持。Tiny11 内置了众多优化特性&#xff0c;如更小的安装体积和更快的启动速度&#xff0c;特别适合有特殊需求或老机型的用户。用户可…

打卡软件——人脸识别综合实现Pro

目录 概要 代码说明 1. 导入库 2. 加载预训练的车辆检测模型 3. 读取视频 4. 初始化变量 5. 逐帧处理视频 6. 处理帧 7. 处理检测结果 8. 计算框的坐标 9. 检查车辆中心是否已计数 10. 绘制检测框 11. 显示车流量 12. 退出条件 13. 释放资源 整体代码 效果展示…

过敏星人能否好好呼吸?约克VRF中央空调从呼吸开始全方位守护

对于包括向先生在内的过敏人群来说,秋天可能是比春天更难熬的坎儿,防不胜防的过敏原,例如空气中飘散的花粉、螨虫、霉菌、宠物毛发和皮屑、屋尘等,因为空气质量问题频频引发的过敏症状,令他们苦不堪言,止不住地打喷嚏、眼睛越揉越痒、起床后就开始擦鼻涕…… 如何才能远离这些…

免费的高质量、美观的甘特图模板

呈现您的项目规划新高度&#xff0c;精选几款高品质、视觉出众的甘特图模板。 甘特图Excel模板-Ganttable系统风格甘特图Excel模板-专业甘特图Excel模板-浅蓝色甘特图Excel模板-深灰色 这些 Excel 甘特图模板均源自 Ganttable 甘特图AI工具的智能生成与导出。利用 Ganttable&a…

Win32动态库介绍及全局函数导出

Windows操作系统中&#xff0c;库分为动态链接库(dll)和静态链接库(lib) 动态库是Windows中实现代码共享的一种方式。它是一个二进制式文件&#xff0c;不可单独运行&#xff0c;需要调用方调用才能运行。在Windows中&#xff0c;动态库可以被多种编程语言所支持。 静态链接库不…

线下线上陪玩系统要多少钱?该怎么搭建?

关于线下线上陪玩系统的价格&#xff0c;由于开发成本、功能复杂度、系统规模以及定制需求等因素的不同&#xff0c;价格差异较大&#xff0c;一般在几千元至几万元不等。具体价格需要根据实际需求和预算进行商议和定制。 搭建线下线上陪玩系统大致可以分为以下几个步骤&#…

论文阅读- On the Feasibility of Fully AI-automated Vishing Attacks

https://arxiv.org/pdf/2409.13793 目录 摘要 INTRODUCTION II. GOALS AND THREAT MODEL III. VIKING A. Architecture B. Interaction with the LLM C. Audio processing D. Call processing E. Implementation IV. EVALUATION METHODOLOGY A. Experiment design …

外卖霸王餐在对接api过程中需要注意哪些方面的问题?

在对接外卖霸王餐 API 过程中&#xff0c;需要注意以下几个方面&#xff1a; 一、合法性与合规性 1.遵守法律法规&#xff1a; 确保你的业务和对 API 的使用符合当地的法律法规&#xff0c;包括消费者权益保护法、电子商务法等。了解并遵守与食品相关的法律法规&#xff0c;…

后台数据管理系统 - 项目架构设计-Vue3+axios+Element-plus(0926)

十四、文章分类添加编辑 [element-plus 弹层] Git仓库&#xff1a;https://gitee.com/msyycn/vue3-hei-ma.git 点击显示弹层 准备弹层 const dialogVisible ref(false)<el-dialog v-model"dialogVisible" title"添加弹层" width"30%">…

【React】组件通信

1. 组件通信 组件间的数据传递 1.1 父传子 步骤&#xff1a; 父组件传递数据——在子组件标签上绑定属性子组件接收数据——子组件通过props参数接收数据 function Son(props) {return <div>{props.value}</div> }function App() {const value 父组件传给子…

从零开学C++:二叉搜索树

引言&#xff1a;在本篇博客当中&#xff0c;我们会将关于二叉树的进阶结构——二叉搜索树&#xff0c;强大的搜索效率让它在数据结构当中变得十分重要&#xff0c;让我们一起来进行学习吧&#xff01; 更多有关C的知识详解可前往个人主页&#xff1a;计信猫 一&#xff0c;二叉…

无人机避障——4D 毫米波雷达 SLAM篇(一)

做无人机避障相关工作&#xff0c;3D毫米波避障测试顺利后&#xff0c;开始做4D毫米波雷达无人机避障遇到4D雷达点云需要进行处理的问题&#xff0c;查阅文献&#xff0c;发现以下这篇文章中的建图方法应该为后续思考的方向&#xff0c;特此将这个开源项目进行复现和学习&#…

《论分布式存储系统架构设计》写作框架,软考高级系统架构设计师

论文真题 分布式存储系统&#xff08;Distributed Storage System&#xff09;通常将数据分散存储在多台独立的设备上。传统的网络存储系统采用集中的存储服务器存放所有数据&#xff0c;存储服务器成为系统性能的瓶颈&#xff0c;也是可靠性和安全性的焦点&#xff0c;不能满…

vue3.0 + element plus 全局自定义指令:select滚动分页

需求&#xff1a;项目里面下拉框数据较多 &#xff0c;一次性请求数据&#xff0c;体验差&#xff0c;效果就是滚动进行分页。 看到这个需求的时候&#xff0c;我第一反应就是封装成自定义指令&#xff0c;这样回头用的时候&#xff0c;直接调用就可以了。 第一步 第二步&…

双十一好物清单分享?五款超值的数码好物分享!

双十一马上就来啦&#xff0c;大家是不是都等着在这个时候买点好东西呀&#xff1f;数码产品可是咱们生活里少不了的&#xff0c;能让咱们的生活更方便、更有意思。我这儿给大家挑了五款特别值的数码好东西&#xff0c;准备来跟大家分享分享&#xff01;快来看看有没有你中意的…

【JAVA基础】JAVA类的拷贝使用示例

文章目录 一、框架介绍二、性能对比三、易用性对比四、使用示例&#xff08;一&#xff09;Apache Commons BeanUtils 使用例子1、第一个例子&#xff1a;两个对象属性个数和名称一样&#xff0c;复制过程2、第二个例子&#xff1a;属性个数和名称不一样&#xff0c;复制过程 &…

UnityHub下载任意版本的Unity包

1)先打开 // 也可以采用2直接打开 2)也可以直接打开 下载存档 (unity.com) 3)关联起来UnityHub即可

Mora:多智能体框架实现通用视频生成

人工智能咨询培训老师叶梓 转载标明出处 尽管已有一些模型能够生成视频&#xff0c;但大多数模型在生成超过10秒的长视频方面存在局限。Sora模型的出现标志着视频生成能力的一个新时代&#xff0c;它不仅能够根据文本提示生成长达一分钟的详细视频&#xff0c;而且在编辑、连接…

【CSS】定位

static ( 默认 )relative ( 相对定位 )absolute ( 绝对定位 )fixed ( 固定定位 )sticky ( 粘性定位 ) 普通文档流&#xff1f;浮动也会让元素脱离文档流&#xff0c;如果不设置浮动所有元素都处于普通文档流中。普通文档流中元素框的位置由元素在HTML中的位置决定&#xff0c;块…