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

leetcode 2360 图中最长的环 题解

news 来源：原创 2025/7/13 16:43:20

题面

给定一个有向图，每个点出度最大为一，现在问你图中最长的环的长度是多少，如果没有环输出 -1， 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105。
题面

解题思路

我们直接说结论，我们从任意一个点出发，用一个数组存下来到达每一个点的最短步数，如果发现一个点之前已经被遍历过了，那么这个点一定是一个环的起点和终点，环的长度是当前的步数减去这个点的最短步数。

下面稍微证明一下，我们来看题目中给出的条件，每一个点最多只有一条出边，那么这个条件告诉了我们两件事情：

  1. 边数比较小；
  2. 图中不存在以下情况：
    在这里插入图片描述

所以当我们遍历的时候，所有经过的点和边形成的一定是一个链型的结构。当发现有一个点重复遍历的时候，一定是返回到了链上前面的某一个点，形成了一个环，我们统计一下答案就好了。

除此之外我们要注意，题目没有保证任意两点之间可以互相到达，当我们遍历一次之后我们还要检查还有没有别的点我们没有遍历。

任意两次遍历是互不影响的，或者说一个环只可能出现在具体的一次遍历当中，所以当我们完成一次遍历的时候，直接把这次的点全部都删了就行，不然复杂度就上来了。

代码

class Solution {
public:int ans = -1; // 最终答案vector<int> dis; // 存最短步数void dfs(int x, int D, vector<int>& edges) // D 表示当前步数{if (dis[x] != 0) // 如果发现之前被遍历过了，说明可能存在环{if (dis[x] == -1) // -1 说明是之前的遍历，不用管return;ans = max(ans, D - dis[x]); // 否则就是存在环，记录答案return;}dis[x] = D; // 维护 disif (edges[x] != -1)dfs(edges[x], D + 1, edges); // 最多只有一个出度，就不用 for 循环了dis[x] = -1; // 遍历完成开始回溯了，直接把这个点删掉}int longestCycle(vector<int>& edges) {const int N = edges.size();dis.resize(100005, 0); for (int i = 0; i < N; i++) // 记得要遍历所有的点if (dis[i] == 0)dfs(i, 1, edges);return ans;}
};










本人能力有限，如有不当之处敬请指教！

相关文章：

leetcode 2360 图中最长的环 题解

题面 给定一个有向图&#xff0c;每个点出度最大为一&#xff0c;现在问你图中最长的环的长度是多少&#xff0c;如果没有环输出 -1&#xff0c; 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105。 题面 解题思路 我们直接说结论&#xff0c;我们从任意一个点出发&#xff0c;用…...

编程日记 2025/7/13 16:43:20

鸿蒙UI开发

鸿蒙UI开发 本文旨在分享一些鸿蒙UI布局开发上的一些建议&#xff0c;特别是对屏幕宽高比发生变化时的应对思路和好的实践。 折叠屏适配 一般情况&#xff08;自适应布局/响应式布局&#xff09; 1.自适应布局 1.1自适应拉伸 左右组件定宽 TypeScript //左右定宽 Row() { …...

编程日记 2025/7/14 10:06:26

华宇TAS应用中间件与晓窗科技智慧校园管理一体化平台完成兼容互认证

近日&#xff0c;华宇TAS应用中间件与安徽晓窗教育科技有限公司&#xff08;以下简称晓窗科技&#xff09;的智慧校园管理一体化平台V1.0完成兼容性认证。经双方联合测试&#xff0c;两款产品在稳定性、安全性以及性能等方面表现优异&#xff0c;可以满足政企客户对于数据安全以…...

编程日记 2025/7/13 21:46:09

Java——数组

一、数组是&#xff1f; 数组就是一个容器&#xff0c;用于存储一批同种类型的数据。 数组变量名中存储的是数组在内存中的地址&#xff0c;数组是一种引用数据类型。 二、静态初始化数组 &#xff08;一&#xff09;定义 即定义数组的时候直接给数组赋值。 &#xff08;…...

编程日记 2025/7/14 9:16:48

MySQL排序详解

MySQL支持两种方式排序filesort和indexindex是指扫描索引本身完成排序&#xff0c;index效率高filesort是指通过内存或者排序文件完成排序&#xff0c;filesort效率低 order by满足两种情况时会使用index排序 order by语句使用索引最左列where条件字段和order by字段组合满足索…...

编程日记 2025/7/14 10:07:30

【python实战】-- 选择解压汇总mode进行数据汇总20250329更新

系列文章目录 文章目录 系列文章目录前言一、功能列表二、程序如下&#xff1a;总结 前言 一、功能列表 该模板用于多功能数据汇总处理&#xff1a; 1、用于解压压缩包&#xff0c;输入指定路径&#xff0c;即可解压多级压缩文件&#xff1b; 2、镜筒反射率、LAB文件汇总&…...

编程日记 2025/7/14 9:08:04

Java 程序员面试题：从基础到高阶的深度解析

引言 Java 作为全球最流行的编程语言之一&#xff0c;其面试题不仅考察候选人的编程能力&#xff0c;更关注对底层原理和架构设计的理解。本文将系统梳理 Java 面试中的高频考点&#xff0c;结合代码示例与原理分析&#xff0c;助您从容应对技术面试。 一、Java 基础语法与核…...

编程日记 2025/7/14 9:31:06

JSP（实验）：带验证码的用户登录

[实验目的] 1&#xff0e;掌握应用request对象获取表单提交的数据。 2&#xff0e;掌握解决获取表单提交数据产生中文乱码的问题。 3&#xff0e;掌握使用response对象进行定时跳转功能。 4&#xff0e;掌握使用session对象完成登录和注销功能。 [实验要求] 设计带验证码…...

编程日记 2025/7/14 9:31:59

【安全运营】关于攻击面管理相关概念的梳理（二）

CYNC&#xff08;持续可见性和网络控制&#xff09; CYNC&#xff08;Continuous Visibility and Network Control&#xff09;即“持续可见性和网络控制”&#xff0c;是一个与网络安全和IT运营管理相关的概念。它强调的是在一个组织的数字环境中&#xff0c;确保对所有资产、…...

编程日记 2025/7/14 9:33:03

【Linux篇】进程入门指南：操作系统中的第一步

步入进程世界&#xff1a;初学者必懂的操作系统概念 一. 冯诺依曼体系结构1.1 背景与历史1.2 组成部分1.3 意义 二. 进程2.1 进程概念2.1.1 PCB&#xff08;进程控制块&#xff09; 2.2 查看进程2.2.1 使用系统文件查看2.2.2 使⽤top和ps这些⽤⼾级⼯具来获取2.2.3 通过系统调用…...

编程日记 2025/7/14 9:58:39

Linux进程状态补充(10)

文章目录 前言一、阻塞二、挂起三、运行R四、休眠D五、四个重要概念总结 前言 上篇内容大家看的云里雾里&#xff0c;这实在是正常不过&#xff0c;因为例如 写实拷贝 等一些概念的深层原理我还没有讲解&#xff0c;大家不用紧张&#xff0c;我们继续往下学习就行&#xff01;&…...

编程日记 2025/7/14 9:44:20

STM32_HAL开发环境搭建【Keil(MDK-ARM)、STM32F1xx_DFP、 ST-Link、STM32CubeMX】

安装Keil(MDK-ARM)【集成开发环境IDE】 我们会在Keil(MDK-ARM)上去编写代码、编译代码、烧写代码、调试代码。 Keil(MDK-ARM)的安装方法&#xff1a; 教学视频的第02分03秒开始看。 安装过程中请修改一下下面两个路径&#xff0c;避免占用C盘空间。 Core就是Keil(MDK-ARM)的…...

编程日记 2025/7/14 1:25:07

全自动数字网络机器人：重塑未来的无形引擎 ——从金融量化到万物互联，为何必须“ALL IN”？

全自动数字网络机器人&#xff1a;重塑未来的无形引擎 ——从金融量化到万物互联&#xff0c;为何必须“ALL IN”&#xff1f; &#xff08;2025年3月29日&#xff09; “未来十年&#xff0c;代码将比石油更具价值。” —— DeepSeek创始人梁文锋 一、数据洪流与AI进化&#…...

编程日记 2025/7/11 5:23:22

每日一题之修建灌木

问题描述 爱丽丝要完成一项修剪灌木的工作。 有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌 木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开 始向左修…...

编程日记 2025/7/14 9:17:48

智能仪表板DevExpress Dashboard v24.2新版亮点：支持.NET 9

使用DevExpress BI Dashboard&#xff0c;再选择合适的UI元素&#xff08;图表、数据透视表、数据卡、计量器、地图和网格&#xff09;&#xff0c;删除相应参数、值和序列的数据字段&#xff0c;就可以轻松地为执行主管和商业用户创建有洞察力、信息丰富的、跨平台和设备的决策…...

编程日记 2025/7/14 9:03:18

ubuntu下终端打不开的排查思路和解决方法

问题现象描述&#xff1a;ubuntu开机后系统桌面显示正常&#xff0c;其他图形化的app也都能打开无异常&#xff0c;唯独只有terminal终端打不开&#xff0c;无论是鼠标点击终端软件&#xff0c;还是ctrlaltt&#xff0c;还是altF2后输入gnome-terminal后按回车&#xff0c;这三…...

编程日记 2025/7/14 9:03:19

鸿蒙项目源码-天气预报app-原创!原创!原创!

鸿蒙天气预报项目源码包运行成功含文档ArkTS语言。 我半个月写的原创作品&#xff0c;请尊重原创。 原创作品&#xff0c;盗版必究&#xff01;&#xff01;&#xff01;&#xff01; 原创作品&#xff0c;盗版必究&#xff01;&#xff01;&#xff01;&#xff01; 原创作品…...

编程日记 2025/7/14 9:41:55

Turtle事件处理（键盘与鼠标交互）

Turtle 提供了 事件驱动编程，允许我们使用 键盘 和 鼠标 控制 Turtle，从而实现交互式绘图。例如，我们可以让 Turtle 响应 按键、鼠标点击 和 拖动 事件，使其根据用户的输入进行移动、旋转或绘制图形。 1. 事件机制概述 Turtle 的事件处理主要依赖 turtle.Screen() 提供的 …...

编程日记 2025/7/14 9:05:22

算法基础——模拟

目录 1 多项式输出 2.蛇形方阵 3.字符串的展开 模拟&#xff0c;顾名思义&#xff0c;就是题⽬让你做什么你就做什么&#xff0c;考察的是将思路转化成代码的代码能⼒。这类题⼀般较为简单&#xff0c;属于竞赛⾥⾯的签到题&#xff08;但是&#xff0c;万事⽆绝对&#xff…...

编程日记 2025/7/14 9:42:37

惠普（HP）和联想（Lenovo）作为全球两大电脑品牌，并不是简单的“拼接电脑”

惠普&#xff08;HP&#xff09;和联想&#xff08;Lenovo&#xff09;作为全球两大电脑品牌&#xff0c;并不是简单的“拼接电脑”&#xff0c;它们都有自己的核心技术、专利设计和生态体系。以下是它们“自己的”核心部分&#xff1a; 1. 关键自研技术 品牌自研技术/专利说明…...

编程日记 2025/7/14 9:35:03

一些练习 C 语言的小游戏

一些练习 C 语言的小游戏 — 1. 猜数字游戏 描述&#xff1a;程序随机生成一个数字&#xff0c;玩家需要猜测这个数字&#xff0c;并根据提示&#xff08;太高或太低&#xff09;调整猜测&#xff0c;直到猜中为止。 功能点&#xff1a; 随机数生成 (rand() 函数)。循环和…...

编程日记 2025/7/14 0:04:46

曲线拟合 | Matlab基于贝叶斯多项式的曲线拟合

效果一览 代码功能 代码功能简述 目标&#xff1a;实现贝叶斯多项式曲线拟合&#xff0c;动态展示随着数据点逐步增加&#xff0c;模型后验分布的更新过程。 核心步骤&#xff1a; 数据生成&#xff1a;在区间[0,1]生成带噪声的正弦曲线作为训练数据。 参数设置&#xff1a…...

编程日记 2025/7/14 9:37:15

Python 序列构成的数组(对序列使用+和_)

对序列使用和* Python 程序员会默认序列是支持 和 * 操作的。通常 号两侧的序列由 相同类型的数据所构成&#xff0c;在拼接的过程中&#xff0c;两个被操作的序列都不会被 修改&#xff0c;Python 会新建一个包含同样类型数据的序列来作为拼接的结果。 如果想要把一个序列…...

编程日记 2025/7/14 9:22:09

洛谷题单1-P5703 【深基2.例5】苹果采购-python-流程图重构

题目描述 现在需要采购一些苹果&#xff0c;每名同学都可以分到固定数量的苹果&#xff0c;并且已经知道了同学的数量&#xff0c;请问需要采购多少个苹果&#xff1f; 输入格式 输入两个不超过 1 0 9 10^9 109 正整数&#xff0c;分别表示每人分到的数量和同学的人数。 输…...

编程日记 2025/7/14 9:14:13

计算机网络 用deepseek帮助整理的复习资料（一）

### 计算机网络基础知识整理 --- #### **一、网络类型** 1. **局域网 (LAN)** - **定义**&#xff1a;覆盖小范围&#xff08;如家庭、教室、公司&#xff09;。 - **特点**&#xff1a;高带宽、低延迟&#xff0c;设备通过交换机互联。 - **示例**&#xff1…...

编程日记 2025/7/10 1:11:45

虚拟电商-话费充值业务（二）话费充值对接供应商模块开发

一、对接供应商模块开发 供应商对接模块chongba_recharge_supplier主要负责的就是调用外部的供应商系统进行充值下单&#xff0c;这种调用是一种基于HTTP协议的调用。 此外在供应商对接模块中主要是实现的业务逻辑有&#xff1a; 1&#xff1a;余额或押金不足情况下的失败轮…...

编程日记 2025/7/14 9:22:08

DeepSeek 助力 Vue3 开发：打造丝滑的表格（Table）之添加行拖拽排序功能示例3，TableView16_03 拖拽视觉反馈示例

前言：哈喽，大家好，今天给大家分享一篇文章！并提供具体代码帮助大家深入理解，彻底掌握！创作不易，如果能帮助到大家或者给大家一些灵感和启发，欢迎收藏+关注哦 💕 目录 DeepSeek 助力 Vue3 开发：打造丝滑的表格（Table）之添加行拖拽排序功能示例3，TableView16_03 拖…...

编程日记 2025/7/14 9:12:29

游戏引擎学习第186天

回顾并规划今天的任务 现在&#xff0c;我们站在了一个关键的时刻&#xff0c;准备突破&#xff0c;拥有一些优秀的性能分析代码。从目前来看&#xff0c;我们已经能够看到时间的消耗情况&#xff0c;我对这一点感到非常兴奋。昨天的直播中我们勉强让一些东西工作了&#xff0…...

编程日记 2025/7/14 9:08:55

树的基础_遍历（蓝桥云课）

一些树上问题&#xff1a; 树的直径&#xff1a; import java.util.*;public class TreeDiameter {static List<List<Integer>> tree; // 用邻接表存储树结构static int[] depth; // 记录每个节点的深度public static void main(String[] args) {S…...

编程日记 2025/7/14 9:27:34

29_项目

目录 http.js 1、先注册账号 register.html 2、再登录 login.html 3、首页 index.html 4 详情 details.html cart.html css index.css register.css details.css 演示 进阶 http.js let baseURL "http://localhost:8888"; let resgiterApi baseURL &…...

编程日记 2025/7/14 9:15:45

vue搭建一个树形菜单项目

首先搭建项目需要先通过步骤搭建一个vue的项目&#xff0c;然后创建一个component文件&#xff0c;里面新建一个index.vue页面来。 这是引入的element-ui组件库里的组件&#xff0c;来实现我的路由&#xff0c;渲染的是我存储的动态路由&#xff0c;所以需要先安装并且引用。 …...

编程日记 2025/7/6 11:06:05

Python包管理完全指南：pip常用命令与最佳实践

一、pip核心功能解析 作为Python官方推荐的包管理工具&#xff0c;pip承担着以下关键职责&#xff1a; 从PyPI&#xff08;Python Package Index&#xff09;仓库安装/卸载第三方库管理项目依赖关系和版本控制支持本地/私有仓库的包安装维护虚拟环境中的包隔离 二、20个必知…...

编程日记 2025/7/10 4:58:36

Eigen 3

本文来源&#xff1a;腾讯元宝 Eigen 3 是一个专注于线性代数运算的高性能 ​C 模板库&#xff0c;广泛应用于科学计算、机器学习、计算机视觉等领域。以下是其核心特性与功能的综合介绍&#xff1a; 1. ​核心定义与设计理念 ​纯头文件库&#xff1a;Eigen 3 无需编译或链接…...

编程日记 2025/7/12 7:49:29

数字化转型国家标准- GB/T 45341-2025《数字化转型管理 参考架构》

GB/T 45341-2025《数字化转型管理 参考架构》 前言一、数字化转型的根本任务二、标准的主要内容2.1、 核心概念2.2、总体框架2.3、 主要视角2.4、过程方法2.5、 发展阶段与水平档次 前言 在工业和信息化部和国家标准化管理委员会的指导下&#xff0c;全国信息化和工业化融合管…...

编程日记 2025/7/10 22:39:31

Redis 源码硬核解析系列专题 - 第三篇：核心数据结构之字典（Dict）

1. 引言 字典（Dict）是Redis的核心数据结构之一，用于实现键值存储（Redis数据库的核心）和内部元数据管理（如客户端状态）。Redis的字典基于哈希表实现，支持高效的增删改查操作。本篇将深入剖析其源码实现，包括哈希表结构、冲突解决和渐进式rehash机制。 2. 字典的结构体…...

编程日记 2025/7/13 11:07:44

JS—异步编程：3分钟掌握异步编程

个人博客&#xff1a;haichenyi.com。感谢关注 一. 目录 一–目录二–引言三–JavaScript 事件循环机制四–定时器的秘密&#xff1a;setTimeout 和 setInterval五–异步编程模型对比 二. 引言 在现代Web开发中&#xff0c;异步编程是提升性能的关键技术。无论是脚本加载&am…...

编程日记 2025/7/10 0:40:24

Linux C语言调用第三方库，第三方库如何编译安装

在 Linux 环境下使用 C 语言调用第三方库时&#xff0c;通常需要先对第三方库进行编译和安装。以下为你详细介绍一般的编译安装步骤&#xff0c;并给出不同类型第三方库&#xff08;如使用 Makefile、CMake 构建系统&#xff09;的具体示例。 一般步骤 1. 获取第三方库源码 …...

编程日记 2025/7/12 2:28:42

gogs私服搭建

一.介绍&#xff1a; gogs是一个用Go语言开发的自助Git服务&#xff0c;目标是简单、快速搭建Git服务&#xff0c; 支持多种平台&#xff0c;包括Linux、Windows等。它类似于GitHub&#xff0c;但更轻量&#xff0c;适合个人或小团队使用&#xff0c; 在简化git服务搭建流程的…...

编程日记 2025/7/11 4:23:01

python和c中作用域的差异

好的&#xff0c;我将详细列举 Python 和 C 语言在作用域规则上的主要差异&#xff0c;并为每种差异提供具体的代码示例&#xff0c;以便更清晰地理解它们之间的不同。 1. 块级作用域&#xff08;Block Scope&#xff09; C 语言 在 C 语言中&#xff0c;任何用 {} 包裹的代…...

编程日记 2025/7/7 19:25:02

C++ 中将函数作为参数传递

C 中将函数作为参数传递 1. 通过指针传递函数 函数可以通过传递函数的地址来作为参数传递&#xff1b;简而言之&#xff0c;就是通过指针实现这一点。 示例代码 #include <iostream> using namespace std;// 定义加法和减法函数 #include <iostream> #include …...

编程日记 2025/7/13 19:00:14

【C++】右值引用与完美转发

目录 一、右值引用&#xff1a; 1、左值与右值&#xff1a; 2、左值引用和右值引用&#xff1a; 二、右值引用的使用场景&#xff1a; 1、左值引用的使用场景&#xff1a; 2、右值引用的使用场景&#xff1a; 移动构造 移动赋值 三、完美转发&#xff1a; 1、万能引用…...

编程日记 2025/7/9 23:32:14

批量合并 PDF 文档，支持合并成单个文档，也支持按文件夹合并 PDF 文档

在日常工作中&#xff0c;合并多个 PDF 文档为一个文件是非常常见的需求。通过合并 PDF&#xff0c;不仅能够更方便地进行管理&#xff0c;还能在特定场景下&#xff08;如批量打印&#xff09;提高效率。那么&#xff0c;当我们需要批量合并多个 PDF 文件时&#xff0c;是否有…...

编程日记 2025/7/10 16:35:08

SQL Server 备份相关信息查看

目录标题 一、统计每个数据库在不同备份目录和备份类型下的备份次数&#xff0c;以及最后一次备份的时间整体功能详细解释 二、查询所有完整数据库备份的信息&#xff0c;包括备份集 ID、数据库名称、备份开始时间和备份文件的物理设备名称&#xff0c;并按备份开始时间降序排列…...

编程日记 2025/7/8 18:36:21

Flutter_学习记录_AppBar中取消leading的占位展示

将leading设置为null将automaticallyImplyLeading设置为false 看看automaticallyImplyLeading的说明&#xff1a; Controls whether we should try to imply the leading widget if null. If true and [AppBar.leading] is null, automatically try to deduce what the leading…...

编程日记 2025/7/12 23:47:07

多省发布！第27届中国机器人及人工智能大赛各赛区比赛通知

01 大赛介绍 中国机器人及人工智能大赛是由中国人工智能学会主办的极具影响力的全国性学科竞赛&#xff0c;旨在推动我国机器人及人工智能技术的创新与应用&#xff0c;促进相关专业的人才培养。作为全国高校学科竞赛A类赛事&#xff0c;该比赛吸引了众多高校和科研机构的积极…...

编程日记 2025/7/10 14:14:54

leetcode199 二叉树的右视图

小问题&#xff1a;if(!q.empty()) 这个条件会导致只处理一层&#xff0c;而不会处理所有层。正确的做法应该是用 while(!q.empty()) 循环处理每一层。 class Solution { public:vector<int> rightSideView(TreeNode* root) {vector<int> res;queue<TreeNode…...

编程日记 2025/7/10 20:09:15

大模型评测框架evalscope、openCompass

一、evalscope使用说明 1、如何使用智增增的接口&#xff1a; VLLM_USE_MODELSCOPETrue evalscope eval \--model qwen2.5-14b-instruct \--api-url https://api.zhizengzeng.com/v1/chat/completions \--api-key skxxx \--eval-type service \--datasets gsm8k \--limit 10 …...

编程日记 2025/7/11 5:11:48

接口自动化——初识pytest

缩写单词含义.passed通过Ffailed失败&#xff08;用例执行时报错&#xff09;Eerror出错&#xff08;fixture执行报错&#xff09;sskipped跳过Xxpassed预期外的通过&#xff08;不符合预期&#xff09;xxfailed预期内的失败&#xff08;符合预期&#xff09; 1.pytest 配置 1…...

编程日记 2025/7/4 18:26:20

SkyWalking实战

1、下载SkyWalking APM 1.手动下载 Downloads | Apache SkyWalkinghttps://skywalking.apache.org/downloads/ 2.链接下载 https://dlcdn.apache.org/skywalking/10.2.0/apache-skywalking-apm-10.2.0.tar.gzhttps://dlcdn.apache.org/skywalking/10.2.0/apache-skywalking-…...

编程日记 2025/7/1 1:18:46

游戏AI实现-GOAP

GOAP原理&#xff1a; GOAP&#xff08;面向目标的行动规划&#xff0c;Goal - Oriented Action Planning&#xff09; 旨在让智能体通过选择一系列行动来达成特定目标。它基于对世界状态的理解&#xff0c;每个行动都有前提条件和效果。智能体通过分析当前世界状态与目标状态…...

编程日记 2025/7/13 9:09:07