亲宝软件园·资讯

展开

C C++ 图中的最长环

Junkman丶 人气:0

题目描述

题目链接: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,期间不断维护环的最大值即可,最后返回这个最大值即可。

复杂度分析

代码实现

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;
    }
};

总结

测试结果:

加载全部内容

相关教程
猜你喜欢
用户评论