C C++ 题解LeetCode2360图中的最长环示例

2024-10-03 15:53:50

题目描述

题目链接：2360. 图中的最长环

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点至多有一条出边。

图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。

请你返回图中的最长环，如果没有任何环，请返回 -1 。

一个环指的是起点和终点是 同一个 节点的路径。

提示:

示例 1：

输入： edges = [3,3,4,2,3]
输出去： 3
解释：图中的最长环是：2 -> 4 -> 3 -> 2 。
这个环的长度为 3 ，所以返回 3 。

示例 2：

输入： edges = [2,-1,3,1]
输出： -1
解释：图中没有任何环。

整理题意

题目给定一张含有 n 个节点的 有向图，且每个节点至多有一条出边。

给定一个整数数组 edges，表示节点 i 到节点 edges[i] 之间有一条有向边（ i 指向 edges[i]）。

规定如果节点 i 没有出边，那么 edges[i] == -1 。

题目让我们返回图中最长的环，如果图中不存在环返回 -1 。

解题思路分析

因为该题所给的图为有向图，且每个节点至多只有一条出边，我们可以从任意一个节点出发，如果能够到达本轮已经遍历过的节点，那么说明能够构成一个新环。维护环的最大值即可。

具体实现

那么我们要怎么记录遍历过的节点是否为本轮遍历过的节点呢？

很容易想到每次都清空一遍标记数组，但是因为题目数据范围的原因，这样做是会超时的。

正确做法：利用一个时间戳来表示每个节点是第几个被遍历到的，那么我们只需记录本轮开始节点的时间戳，当遇到已经遍历过的节点时判断该节点的时间戳与本轮开始节点的时间戳大小关系即可：

如果大于等于本轮开始节点的时间戳：说明是本轮遍历到新的一个环；
否则仅仅表示遍历到之前遍历过的节点，没有构成新的环（因为之前遍历过的节点如果有环也已经记录过了）

初始化环的最大值为 -1，期间不断维护环的最大值即可，最后返回这个最大值即可。

复杂度分析

时间复杂度：O(n)，其中 n 为 edges 的长度，也就是点的个数。
空间复杂度：O(n)。

代码实现

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        // mp[i] = j 表示节点 i 是第 j 个遍历到的
        int mp[n];
        memset(mp, 0, sizeof(mp));
        int ans = -1;
        // k 进行计数
        int k = 1;
        for(int i = 0; i < n; i++){
            // 从没有遍历过的点作为起点
            if(mp[i] == 0){
                int t = i;
                // 找到第一个遍历过的节点
                while(mp[t] == 0){
                    mp[t] = k++;
                    t = edges[t];
                    if(t == -1) break;
                }
                // 利用时间戳计算环的长度，取最大值
                if(t != -1 && mp[t] >= mp[i]){
                    ans = max(ans, k - mp[t]);
                }
            }
        }
        return ans;
    }
};

总结

该题的核心思想为记录每个节点被遍历到的时间戳，通过 时间戳来实现找新环的逻辑。
因为是有向图且每个节点至多有一个出度，所以可以利用时间戳的方式来实现，需要注意这个前提条件。

测试结果：

以上就是C C++ 题解LeetCode2360图中的最长环示例的详细内容，更多关于C C++ 图中的最长环的资料请关注我们其它相关文章！

C++实现LeetCode(347.前K个高频元素)

[LeetCode] 347. Top K Frequent Elements 前K个高频元素 Given a non-empty array of integers, return the k most frequent elements. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Note: You may assume
C++ Leetcode实现从英文中重建数字

目录题目分析代码题目分析首先我们先分析每个字母的组成,然后发现一些字符只在一个单词中出现,我们先去统计一下这些单词个数. z,w,u,x,g都只出现在一个数字中,也就是0,2,4,6,8,我们用哈希表统计一下s字符串中各个字符的数量,就可以知道0,2,4,6,8的数量,然后我们注意一下只在两个数字中出现的字符. h 只在 3,8 中出现.由于我们已经知道了 8 出现的次数,因此可以计算出 3 出现的次数. f 只在 4,5 中出现.由于我们已经知道了 4 出现的次数,因此可以计算出
C C++ LeetCode题解在二叉树中增加一行示例详解

目录题目描述整理题意解题思路分析层序遍历(广度优先搜索) 递归(深度优先搜索) 具体实现复杂度分析代码实现层序遍历(广度优先搜索) 递归(深度优先搜索) 总结题目描述题目链接:623. 在二叉树中增加一行给定一个二叉树的根 root 和两个整数 val 和 depth ,在给定的深度 depth 处添加一个值为 val 的节点行. 注意,根节点 root 位于深度 1 . 加法规则如下: 给定整数 depth,对于深度为 depth - 1 的每个非空树节点 cur ,创建两
C++实现LeetCode数组练习题

目录 1.存在重复元素 2.最大子序和 3.两数之和 4.合并两个有序数组 5.两个数组的交集II 6.买卖股票的最佳时机 7.杨辉三角 8.重塑矩阵 9.有效的数独 10.矩阵置零总结 1.存在重复元素排序数组,之后遍历是否有重复的元素 public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for(int i=1;i<nums.length;i++){ if(nums[i-1]==nums[i]){ return
C C++算法题解LeetCode1408数组中的字符串匹配

目录题目描述整理题意解题思路分析优化具体实现复杂度分析代码实现暴力暴力 + 优化 KMP 总结题目描述题目链接:1408. 数组中的字符串匹配给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词.请你按任意顺序返回 words 中是其他单词的子字符串的所有单词. 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串. 提示: 示例 1: 输入:wo
C++LeetCode数据结构基础详解

目录一.只出现一次的数字二.多数元素三.三数之和总结一.只出现一次的数字遍历一遍数组利用异或的特性来实现(相同为0,相异为1 ) 例如[4,1,2,1,2] 4和1异或为5 5和2异或为7 7和1异或为6 6和2异或为4 这样就能找出唯一的数字了 public int singleNumber(int[] nums) { int res=0; for(int i=0;i<nums.length;i++){ res=res^nums[i]; } return res; } 二.多数元素
C C++ 题解LeetCode2360图中的最长环示例

目录题目描述整理题意解题思路分析具体实现复杂度分析代码实现总结题目描述题目链接:2360. 图中的最长环给你一个 n 个节点的有向图 ,节点编号为 0 到 n - 1 ,其中每个节点至多有一条出边. 图用一个大小为 n 下标从 0 开始的数组 edges 表示,节点 i 到节点 edges[i] 之间有一条有向边.如果节点 i 没有出边,那么 edges[i] == -1 . 请你返回图中的最长环,如果没有任何环,请返回 -1 . 一个环指的是起点和终点是同一个
iOS实现从背景图中取色的代码

本文实例讲解了iOS从背景图中取色的代码,分享给大家供大家参考,具体内容如下实现代码: void *bitmapData; //内存空间的指针,该内存空间的大小等于图像使用RGB通道所占用的字节数. static CGContextRef CreateRGBABitmapContext (CGImageRef inImage) { CGContextRef context = NULL; CGColorSpaceRef colorSpace; int bitmapByteCount; int
jQuery插件echarts设置折线图中折线线条颜色和折线点颜色的方法

本文实例讲述了jQuery插件echarts设置折线图中折线线条颜色和折线点颜色的方法.分享给大家供大家参考,具体如下: 1.问题背景设计一条折线图,但是图形中不用插件自带的颜色,需要自定义线条和折点的颜色 2.实现源码 (1)图形自分配颜色 <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>echarts-设置折线图中折线线条颜色和折线点颜色</t
python 实现在一张图中绘制一个小的子图方法

有时候为了直观展现图的信息,可以在大图中添加小子图的方式进行数据分析,如下图所示: 具体的代码如下:该图连接了数据库,当然重要的不是数据展示,而是添加子图的方法. import matplotlib.pyplot as plt import MySQLdb as mdb import numpy as np from mpl_toolkits.axes_grid1.inset_locator import inset_axes from mpl_toolkits.axes_grid1.inset
Python利用matplotlib做图中图及次坐标轴的实例

图中图准备数据 import matplotlib.pyplot as plt fig = plt.figure() x = [1, 2, 3, 4, 5, 6, 7] y = [1, 3, 4, 2, 5, 8, 6] - 大图首先确定大图左下角的位置以及宽高: 注意,4个值都是占整个figure坐标系的百分比.在这里,假设figure的大小是10x10,那么大图就被包含在由(1, 1)开始,宽8,高8的坐标系内. # below are all percentage left, bott
Python在Matplotlib图中显示中文字体的操作方法

1. 说明本篇主要针对在Ubuntu系统中,matplotlib显示不了中文的问题,尤其是在无法安装系统字体的情况下,解决Python绘图时中文显示的问题. 2. 在系统中安装字体 $ fc-list :lang=zh # 查看中文字体名称及其安装路径,相对于英文字体,中文字体文件一般较大. 如果无中文字体,可使用apt-get安装,具体方法如下: $ apt-cache search font|grep Chinese # 查看可安装的中文字体 $ sudo apt-get in
java查找图中两点之间所有路径

本文实例为大家分享了java查找图中两点之间所有路径的具体代码,基于邻接表,供大家参考,具体内容如下图类: package graph1; import java.util.LinkedList; import graph.Graph.edgeNode; public class Graph { class EdgeNode{ int adjvex; EdgeNode nextEdge; } class VexNode{ int data; EdgeNode firstEdge; boolea
Python使用Dijkstra算法实现求解图中最短路径距离问题详解

本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题.分享给大家供大家参考,具体如下: 这里继续前面一篇<Python基于Floyd算法求解最短路径距离问题>的内容,这里要做的是Dijkstra算法,与Floyd算法类似,二者的用途均为求解最短路径距离,在图中有着广泛的应用,二者的原理都是老生常谈了,毕竟本科学习数据结构的同学是不可能不学习这两个算法的,所以在这里我也不再累赘,只简单概述一下这个算法的核心思想: Dijkstra算法的输入有两个参数,一个是原始的数据矩
在matplotlib的图中设置中文标签的方法

其实就是通过 FontProperties来设置的,请参考以下代码: import matplotlib.pyplot as plt from matplotlib.font_manager import FontProperties font = FontProperties(fname=r"c:\windows\fonts\msyh.ttc", size=15) plt.title("散点图练习", fontproperties=font) plt.scatte
python matplotlib如何给图中的点加标签

这篇文章主要介绍了python matplotlib给图中的点加标签,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下在写论文用到matplotlib画散点图,想着如果能把每个点对应的ID打在点的旁边就好了,经过一番搜索,最后找到了方法. 首先是打点,先把所有的点画好,举例如下: p1 = ax.scatter(X[:,0], X[:,1], marker = '*', color = 'r', label='1', s=10) 再依次给每个点打