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

是否存在路径(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.lqws.cn/news/166159.html

相关文章:

  • Java-IO流之缓冲流详解
  • 实现基于Yolo的异常聚集算法
  • 经典算法:回文链表
  • 计算机操作系统知识点总结④【完】
  • 2025年渗透测试面试题总结-ali 春招内推电话1面(题目+回答)
  • linux应急响应检查脚本
  • web第十次课后作业--Mybatis的增删改查
  • Java常用工具类方法详解及使用案例
  • ABP VNext 在 Kubernetes 中的零停机蓝绿发布
  • 用 NGINX 构建高效 POP3 代理`ngx_mail_pop3_module`
  • 计算机组成原理(计算篇)
  • 在MATLAB中使用自定义的ROS2消息
  • 本地部署大模型实战:使用AIStarter一键安装Ollama+OpenWeb教程(含最新版本更新指南)
  • 【python深度学习】Day 45 Tensorboard使用介绍
  • 主流消息队列对比
  • 基于protobuf + iceoryx实现共享内存上的零拷贝
  • vue和uniapp聊天页面右侧滚动条自动到底部
  • python执行测试用例,allure报乱码且未成功生成报告
  • 学习路之PHP--webman安装及使用、webman/admin安装
  • Mobile App UI自动化locator
  • Jenkins | Jenkins构建成功服务进程关闭问题
  • Redis数据持久化机制深度解析
  • 从零开始的嵌入式学习day33
  • 【Fifty Project - D33】
  • select、poll、epoll 与 Reactor 模式
  • UI学习—cell的复用和自定义cell
  • linux 串口调试命令 stty
  • SELinux是什么以及如何编写SELinux策略
  • Git操作记录
  • 知识蒸馏:从模型输出到深层理解