2360 图中的最长环

题目链接

2360. 图中的最长环

分析

遍历每一个节点，并且记录下遍历到的时间

由于每一个节点只有一个出边，那么从任意节点开始遍历，都会出现以下三种情况中的一种：

(1) 走到一个没有出边的节点

(2) 走到一个遍历过的节点，但该节点在之前的遍历中就已经访问过

(3) 走到一个遍历过的节点，该节点在这次遍历中访问过

对于前两种情况来说，可以直接结束循环

对于第三种情况来说，设该节点第一次被遍历到的时间为 $a$ ，第二次时间为 $b$，那么我们找到了一个长度为 $b- a$ 的环

代码实现

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        int ans = -1;
        int cur_time = 0;
        vector<int> times(n);
  
        for(int i = 0; i < n; ++i) {
            if(times[i])
                continue;

            int u = i, start_time = cur_time;

            while(u != -1) {
                cur_time++;
                if(times[u]) {
                    if(times[u] > start_time) {
                        ans = max(ans, cur_time - times[u]);
                    }
                    break;
                }
                times[u] = cur_time;
                u = edges[u];
            }
        }

        return ans; 
    }
};

复杂度分析

• 时间复杂度：$O(n)$，我们只访问每个节点一次
• 空间复杂度：$O(n)$