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

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 个顶点的 双向 图&#xff0c;每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示&#xff0c;其中 edges[i] [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接&#xff0c;并且不存在与自身相连的顶点。 返回图中 …...

C++学习——类其实也是一种作用域

以下内容源于C语言中文网的学习与整理&#xff0c;非原创&#xff0c;如有侵权请告知删除。 其实也是一种作用域&#xff0c;每个类都会定义它自己的作用域。在类的作用域之外&#xff0c;普通的成员只能通过对象&#xff08;可以是对象本身&#xff0c;也可以是对象指针或对象…...

Seata入门系列【4】undo_log、global_table、branch_table、lock_table字段及作用详解

1 客户端 1.1 undo_log 在AT模式中&#xff0c;需要在参与全局事务的数据库中&#xff0c;添加一个undo_log表&#xff0c;建表语句如下&#xff1a; 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 中&#xff0c;可以使用 DateFormat 类和 SimpleDateFormat 类来格式化日期&#xff0c;下面详细介绍这两…...

centos 7 lamp owncloud

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

屏幕亮度调节保护您的眼睛

官方下载地址&#xff1a; 安果移动 视频演示&#xff1a;屏幕亮度调节-保护您的眼睛_哔哩哔哩_bilibili 嗨&#xff0c;亲爱的用户&#xff0c;你是否有过这样的体验&#xff1a;夜晚安静的时刻&#xff0c;想要在抖音上看看热门的舞蹈、在快手上发现生活的 趣味、或是在哔…...

CentOS Linux下CMake二进制文件安装并使用Visual Studio调试

cmake安装——二进制安装(很简单&#xff0c;推荐&#xff01;&#xff01;) 1&#xff09;下载二进制包。首先就是官网下载二进制安装包(我们是64位系统&#xff0c;就下载对应的包)&#xff0c;这里。 例如&#xff1a;在/home/DOWNLOAD目录下执行&#xff0c;即下载二进制…...

ASP.net相关目录,相关配置文件和.后缀名解释

App_Data&#xff1a;用于存储应用程序的数据文件&#xff0c;例如数据库文件或其他本地文件。 App_Start&#xff1a;包含应用程序的启动配置文件&#xff0c;例如路由配置、日志配置等。 Content&#xff1a;存放应用程序的静态资源文件&#xff0c;如 CSS、JavaScript、图…...

一键批量转换,轻松将TS视频转为MP4视频,实现更广泛的播放和分享!

在享受精彩视频内容的同时&#xff0c;有时我们可能会面临一个问题&#xff1a;某些视频格式可能不太适合我们的播放设备或分享平台。特别是TS格式的视频&#xff0c;在一些情况下可能无法直接播放或上传。但是不用担心&#xff0c;因为我们为您提供了一款强大的视频剪辑工具&a…...

【Redis】使用Java客户端操作Redis

目录 引入jedis依赖连接Redis命令get/setexists/delkeysexpire/ttltype 引入jedis依赖 连接Redis 命令 get/set exists/del keys expire/ttl type...

BSPHP 未授权访问 信息泄露

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

Learning Sample Relationship for Exposure Correction 论文阅读笔记

这是中科大发表在CVPR2023的一篇论文&#xff0c;提出了一个module和一个损失项&#xff0c;能够提高现有exposure correction网络的性能。这已经是最近第三次看到这种论文了&#xff0c;前两篇分别是CVPR2022的ENC&#xff08;和这篇文章是同一个一作作者&#xff09;和CVPR20…...

Vue项目 -- 解决Eslint导致的console报错问题

在利用vue-cli3构建的项目中引入eslint进行语法检查时&#xff0c;使用console.log(‘xxx’)时&#xff0c;控制台抛出了Unexpected console statement (no-console) 异常&#xff0c; 例&#xff1a;一使用console就提示报错 解决办法是&#xff1a; 在 .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 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 示例 1&#xff1a; 输入&#xff1a;digits “23” 输出&…...

使用 Apache Kafka 进行发布-订阅通信中的微服务

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

valarray 包含对象成员的类(cpp14章)

C代码重用 1.公有继承可以实现 2.包含、私有继承、保护继承用于实现has-a关系&#xff0c;即新的类将包含另一个类的对象。 &#xff08;使用这样类成员&#xff1a;本身是另外一个类对象称为包含 &#xff08;组合或层次化&#xff09;。&#xff09; 3.函数模板、类模…...

2023双11笔记本电脑候选名单(截止2023.10.13的价格,双十一活动可能会更便宜一点)

以下是我最近几天查阅抖音,B站,知乎,百度,朋友后候选出来的一些6000-8000的游戏本电脑,标绿的属性是相比之下较为优秀的 附上几个网上的CPU和显卡排行网站 CPU性能排行榜 - CPU天梯图 - 最强CPU2023(较为全面的CPU排行,收录四千多款) 笔记本性能排行榜 - 快科技天梯榜 笔记本CP…...

Springcloud笔记(4)-客户端负载均衡Ribbon

Ribbon是一个基于HTTP和TCP的客户端负载均衡工具&#xff0c;不需要独立部署&#xff0c;几乎存在于每一个springcloud构建的微服务和基础设施中。 微服务间调用&#xff0c;API网关的请求转发都通过Ribbon实现。 负载均衡 通常所说的负载均衡都是指的服务端负载均衡&#xf…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

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

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

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...