C C++ 图中的最长环

题目描述

题目链接：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;
    }
};

总结

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

测试结果：