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

是否存在路径(FIFOBB算法)

题目描述
一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。
输入
第一行两个整数,分别表示n 和 e 的值(1 <= n <= 2 * 10^5,  0 <= e <= 2 * 10^5);
下面e行,每行两个整数,分别表示一条边的两个顶点;
最后一行两个整数,分别表示 source 和 destination的值。
输出
若存在从顶点 source到顶点 destination的路径,则输出true;否则,输出false。
样例输入 Copy
3 3
0 1
1 2
2 0
0 2
样例输出 Copy
true

#include<bits/stdc++.h>
using namespace std;
int n,e;
int main ()
{cin>>n>>e;vector<vector<int>> graph(n);for(int i=0;i<e;i++){int u,v;cin>>u>>v;graph[u].push_back(v);graph[v].push_back(u);}int s,d;cin>>s>>d;if(s==d){cout<<"true"<<endl;return 0;}vector<bool>visited(n,false);queue<int>q;q.push(s);visited[s]=true;while(!q.empty()){int current=q.front();q.pop();for(int i=0;i<graph[current].size();i++){int jb=graph[current][i];if(!visited[jb]){if(jb==d){cout<<"true"<<endl;return 0;}visited[jb]=true;q.push(jb);}}}cout<<"false"<<endl;return 0;
}
//by crtzk7

http://www.xdnf.cn/news/12425.html

相关文章:

  • JupyterNotebook全能指南:从入门到精通
  • LangchainRAG you need - 段落拆分
  • Setting搜索 ===》了解是如何初始搜索索引以及去掉控件搜索
  • exp1_code
  • 腾讯云服务器端口怎么全部打开?CVM和轻量端口开通教程
  • 【杂谈】-吉卜力化(Ghiblified ) AI 图像:艺术与隐私的交织
  • 06.最长连续序列
  • 我的创作纪念日——聊聊我想成为一个创作者的动机
  • 总结这几个月来我和AI一起开发并上线第一个应用的使用经验
  • 数据融合是什么?进行数据融合的4大关键环节!
  • 前端面试准备-7
  • 从 Stdio 到 HTTP SSE,在 APIPark 托管 MCP Server
  • PasteForm(ABP)框架之实现更加灵活的类似多租户的归属过滤功能,比如只能查看自己的相关数据
  • Abaqus分析步与输出:
  • 【leetcode】347. 前k个高频元素
  • 利率的计量
  • VIN码车辆识别码解析接口如何用C#进行调用?
  • 如何利用Elastic Stack(ELK)进行安全日志分析
  • 常见串口种类介绍
  • 一、ES6-let声明变量【解刨分析最详细】
  • 右值引用和移动语义
  • 酷黑NBA足球赛事直播源码体育直播M39模板赛事源码
  • redis数据过期策略、淘汰策略
  • RADIUS-管理员获取共享密钥
  • 【CPU】英特尔酷睿Ultra 5 225H与Ultra7 258V(Lunar Lake架构)PK
  • [蓝桥杯]航班时间
  • 【.net core】天地图坐标转换为高德地图坐标(WGS84 坐标转 GCJ02 坐标)
  • 六、数据库的安全性
  • C++11 中 final 和 override 从入门到精通
  • 在 Spring Boot 中使用 JSP