C++算法:图中的最短环
题目
现有一个含 n 个顶点的 双向 图,每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示,其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接,并且不存在与自身相连的顶点。
返回图中 最短 环的长度。如果不存在环,则返回 -1 。
环 是指以同一节点开始和结束,并且路径中的每条边仅使用一次。
2 <= n <= 1000
1 <= edges.length <= 1000
edges[i].length == 2
0 <= ui, vi < n
ui != vi
不存在重复的边
分析
返回还是真环
利用BFS求到A的最短距离,B和C到A的距离都为1,处理BC是发现B和C都已经和A连通,说明存在环。注意:求EFG到点D的距离,处理完DE ED EF FE FG后,处理GF,发现F和G都和D连通。判断是返回,还是真环有两种思路:
一,记录已经使用的双向边,枚举新边的时候,忽略。此方案容易理解。
二,记录各点的最短距离的前一点。此方案性能。
各点都要BFS
如果以H为源点,则最短的环长4。以k为源点,最短的环是3。
多个连通区域
由于所有点都会作为起点,所以所有点都会处理。和起点不连通的点不会重复处理。
不会遗漏任意环
某个包括x的奇数长度的环,假定其长度为len2+1,环上有两个点距离x为len,假定先处理的为x1,后处理的为x2。处理x1->x2是发现此环。假定此环长为偶数,假定其长度为len2+2。环上有两个点距离x为len,假定先处理的为x1,后处理的为x2。距离x为len+1的点为x3,则处理x2->x3时,发现此环。
不会误判环
发现cur和next都和源点连通,那说明next在cur之前已经处理,也就是vDis[next] <= vDis[cur]。vDis[next]不会比v[cur]小2,否则源点->next->cur更短。也就是vDis[next]和vDis[cur]相等或少1。源点到next的最短路径,不会包括cur,否则vDis[next]大于v[cur]。两者相等的情况,cur的最短路径不会包括next。少1的情况,如果cur的最短路径包括next,则最后一条边是next->cur。
方案一代码
class Solution {
public:
int findShortestCycle(int n, vector<vector>& edges) {
CNeiBo2 neiBo(n, edges, false);
for (int i = 0; i < n; i++)
{
Do(neiBo.m_vNeiB, i);
}
return (INT_MAX == m_iMinCycle) ? -1 : m_iMinCycle;
}
void Do(const vector<vector>& vNeiB, int src)
{
int n = vNeiB.size();
vector<unordered_set> setHas(n);
vector vDis(n, -1);
queue q;
vDis[src] = 0;
q.emplace(src);
while (q.size())
{
const auto cur = q.front();
q.pop();
for (const auto& next : vNeiB[cur])
{
if (setHas[next].count(cur))
{
continue;
}
setHas[cur].emplace(next);
if (-1 != vDis[next])
{
m_iMinCycle = min(m_iMinCycle, vDis[cur] + vDis[next] + 1);
continue;
}
vDis[next] = vDis[cur] + 1;
q.emplace(next);
}
}
}
int m_iMinCycle = INT_MAX;
};
方案二代码
class Solution {
public:int findShortestCycle(int n, vector<vector<int>>& edges) {CNeiBo2 neiBo(n, edges, false);for (int i = 0; i < n; i++){Do(neiBo.m_vNeiB, i);}return (INT_MAX == m_iMinCycle) ? -1 : m_iMinCycle;}void Do(const vector<vector<int>>& vNeiB, int src){int n = vNeiB.size();vector<int> vDis(n, -1), vPre(n,-1);queue<int> q;vDis[src] = 0;vPre[src] = -1;q.emplace(src);while (q.size()){const auto cur = q.front();q.pop();for (const auto& next : vNeiB[cur]){ if (-1 != vDis[next]){if (vPre[cur] != next){m_iMinCycle = min(m_iMinCycle, vDis[cur] + vDis[next] + 1);}continue;}vDis[next] = vDis[cur] + 1;vPre[next] = cur;q.emplace(next);}} }int m_iMinCycle = INT_MAX;
};
方案三
方案一和方案二时间复杂度都是O(n^2),方案一比方案二慢。方案三相比方案一,稍稍提速。
void Do(const vector<vector>& vNeiB, int src)
{
int n = vNeiB.size();
vector<int> vDis(n, -1);
queue<int> q;
vDis[src] = 0;
q.emplace(src);
while (q.size())
{const auto cur = q.front();q.pop();for (const auto& next : vNeiB[cur]){if (m_vHasDo[next][cur]){continue;}m_vHasDo[cur][next] = 1;if (-1 != vDis[next]){m_iMinCycle = min(m_iMinCycle, vDis[cur] + vDis[next] + 1);continue;}vDis[next] = vDis[cur] + 1;q.emplace(next);}
}
}
2023年4月版本
class Solution {
public:
int findShortestCycle(int n, vector<vector>& edges) {
m_iN = n;
m_vNeiB.resize(n);
for (const auto&v : edges)
{
m_vNeiB[v[0]].emplace_back(v[1]);
m_vNeiB[v[1]].emplace_back(v[0]);
}
for (int i = 0; i < n; i++){bfs(i);}return (INT_MAX == m_iRet) ? -1 : m_iRet;
}
void bfs(int iRoot)
{std::vector<int> vDis(m_iN, -1);vDis[iRoot] = 0;std::queue<pair<int,int>> que;que.emplace(iRoot, -1);//当前节点,父节点while (que.size()){const int iPre = que.front().first;const int iPrePre = que.front().second;que.pop();for (const auto& next : m_vNeiB[iPre]){if (-1 == vDis[next]){vDis[next] = vDis[iPre] + 1;que.emplace(next, iPre);}else{if (next == iPrePre){continue;}m_iRet = min(m_iRet, vDis[iPre] + 1 + vDis[next]);}}}
}
vector<std::vector<int>> m_vNeiB;int m_iN;
int m_iRet = INT_MAX;
};
其它
视频课程
如果你觉得复杂,想从简单的算法开始,可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
相关文章:

C++算法:图中的最短环
题目 现有一个含 n 个顶点的 双向 图,每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示,其中 edges[i] [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接,并且不存在与自身相连的顶点。 返回图中 …...
C++学习——类其实也是一种作用域
以下内容源于C语言中文网的学习与整理,非原创,如有侵权请告知删除。 其实也是一种作用域,每个类都会定义它自己的作用域。在类的作用域之外,普通的成员只能通过对象(可以是对象本身,也可以是对象指针或对象…...

Seata入门系列【4】undo_log、global_table、branch_table、lock_table字段及作用详解
1 客户端 1.1 undo_log 在AT模式中,需要在参与全局事务的数据库中,添加一个undo_log表,建表语句如下: SET NAMES utf8mb4; SET FOREIGN_KEY_CHECKS 0;-- ---------------------------- -- Table structure for undo_log -- --…...
虚幻引擎:数据表格的C++常用API
1.将数据表格中的所有数据存到一个数组中 //参数1 // 错误提示 //参数2 // 存储的数组 TArray<FKeyInfoHeader*> array; KeyInfoDT->GetAllRows<FKeyInfoHeader>(TEXT("错误"),array); 2.获取表格中所有的行名称 TArray<FName>array; …...
Java日期格式化(DateFormat类和SimpleDateFormat类)
格式化日期表示将日期/时间格式转换为预先定义的日期/时间格式。例如将日期“Fri May 18 15:46:24 CST2016” 格式转换为 “2016-5-18 15:46:24 星期五”的格式。 在 java 中,可以使用 DateFormat 类和 SimpleDateFormat 类来格式化日期,下面详细介绍这两…...

centos 7 lamp owncloud
OwnCloud是一款开源的云存储软件,基于PHP的自建网盘。基本上是私人使用,没有用户注册功能,但是有用户添加功能,你可以无限制地添加用户,OwnCloud支持多个平台(windows,MAC,Android&a…...

屏幕亮度调节保护您的眼睛
官方下载地址: 安果移动 视频演示:屏幕亮度调节-保护您的眼睛_哔哩哔哩_bilibili 嗨,亲爱的用户,你是否有过这样的体验:夜晚安静的时刻,想要在抖音上看看热门的舞蹈、在快手上发现生活的 趣味、或是在哔…...
CentOS Linux下CMake二进制文件安装并使用Visual Studio调试
cmake安装——二进制安装(很简单,推荐!!) 1)下载二进制包。首先就是官网下载二进制安装包(我们是64位系统,就下载对应的包),这里。 例如:在/home/DOWNLOAD目录下执行,即下载二进制…...
ASP.net相关目录,相关配置文件和.后缀名解释
App_Data:用于存储应用程序的数据文件,例如数据库文件或其他本地文件。 App_Start:包含应用程序的启动配置文件,例如路由配置、日志配置等。 Content:存放应用程序的静态资源文件,如 CSS、JavaScript、图…...

一键批量转换,轻松将TS视频转为MP4视频,实现更广泛的播放和分享!
在享受精彩视频内容的同时,有时我们可能会面临一个问题:某些视频格式可能不太适合我们的播放设备或分享平台。特别是TS格式的视频,在一些情况下可能无法直接播放或上传。但是不用担心,因为我们为您提供了一款强大的视频剪辑工具&a…...

【Redis】使用Java客户端操作Redis
目录 引入jedis依赖连接Redis命令get/setexists/delkeysexpire/ttltype 引入jedis依赖 连接Redis 命令 get/set exists/del keys expire/ttl type...

BSPHP 未授权访问 信息泄露
漏洞描述 BSPHP 存在未授权访问 泄露用户 IP 和 账户名信息 漏洞复现 访问url: 构造payload访问: /admin/index.php?madmin&clog&atable_json&jsonget&soso_ok1&tuser_login_log&page1&limit10&bsphptime16004073…...

Learning Sample Relationship for Exposure Correction 论文阅读笔记
这是中科大发表在CVPR2023的一篇论文,提出了一个module和一个损失项,能够提高现有exposure correction网络的性能。这已经是最近第三次看到这种论文了,前两篇分别是CVPR2022的ENC(和这篇文章是同一个一作作者)和CVPR20…...

Vue项目 -- 解决Eslint导致的console报错问题
在利用vue-cli3构建的项目中引入eslint进行语法检查时,使用console.log(‘xxx’)时,控制台抛出了Unexpected console statement (no-console) 异常, 例:一使用console就提示报错 解决办法是: 在 .eslintrc.js 文件中…...
uni-app 在已有的数据对象中动态添加更多的数据对象
原数据对象 flowData: {list: [], // 数据值column: 2, // 瀑布列数columnSpace: 2 // 瀑布列宽间距 } 动态添加后的数据对象 flowData: {list: [], // 数据值column: 2, // 瀑布列数columnSpace: 2, // 瀑布列宽间距column_1: [],column_2: [] } 动态添加更多的数据对象的…...

【LeetCode】17. 电话号码的字母组合
1 问题 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例 1: 输入:digits “23” 输出&…...

使用 Apache Kafka 进行发布-订阅通信中的微服务
发布-订阅消息系统在任何企业架构中都发挥着重要作用,因为它可以实现可靠的集成,而无需紧密耦合应用程序。在解耦的系统之间共享数据的能力并不是一个容易解决的问题。 考虑一家拥有多个使用不同语言和平台独立构建的应用程序的企业。它需要响应地共享数…...

valarray 包含对象成员的类(cpp14章)
C代码重用 1.公有继承可以实现 2.包含、私有继承、保护继承用于实现has-a关系,即新的类将包含另一个类的对象。 (使用这样类成员:本身是另外一个类对象称为包含 (组合或层次化)。) 3.函数模板、类模…...
2023双11笔记本电脑候选名单(截止2023.10.13的价格,双十一活动可能会更便宜一点)
以下是我最近几天查阅抖音,B站,知乎,百度,朋友后候选出来的一些6000-8000的游戏本电脑,标绿的属性是相比之下较为优秀的 附上几个网上的CPU和显卡排行网站 CPU性能排行榜 - CPU天梯图 - 最强CPU2023(较为全面的CPU排行,收录四千多款) 笔记本性能排行榜 - 快科技天梯榜 笔记本CP…...
Springcloud笔记(4)-客户端负载均衡Ribbon
Ribbon是一个基于HTTP和TCP的客户端负载均衡工具,不需要独立部署,几乎存在于每一个springcloud构建的微服务和基础设施中。 微服务间调用,API网关的请求转发都通过Ribbon实现。 负载均衡 通常所说的负载均衡都是指的服务端负载均衡…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...

Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...

GraphRAG优化新思路-开源的ROGRAG框架
目前的如微软开源的GraphRAG的工作流程都较为复杂,难以孤立地评估各个组件的贡献,传统的检索方法在处理复杂推理任务时可能不够有效,特别是在需要理解实体间关系或多跳知识的情况下。先说结论,看完后感觉这个框架性能上不会比Grap…...

【靶场】XXE-Lab xxe漏洞
前言 学习xxe漏洞,搭了个XXE-Lab的靶场 一、搭建靶场 现在需要登录,不知道用户名密码,先随便试试抓包 二、判断是否存在xxe漏洞 1.首先登录抓包 看到xml数据解析,由此判断和xxe漏洞有关,但还不确定xxe漏洞是否存在。 2.尝试xxe 漏洞 判断是否存在xxe漏洞 A.send to …...
Caliper 配置文件解析:config.yaml 和 fisco-bcos.json 附加在caliper中执行不同的合约方法
Caliper 配置文件解析:config.yaml 和 fisco-bcos.json Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO…...