LeetCode 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.length
2 <= n <= 105
-1 <= edges[i] < n
edges[i] != i

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-cycle-in-a-graph
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对于内向基环树的概念和性质，我之前在 2127. 参加会议的最多员工数 的题解中作了详细介绍，本文不再赘述（把我那篇题解的代码拿来改一改就能过）。

除了使用那篇题解中的通用做法（拓扑排序）外，我们还可以利用时间戳来实现找环的逻辑。

具体来说，初始时间戳clock=1，首次访问一个点 x 时，记录访问这个点的时间time[x]=clock，然后将 clock 加一。

如果首次访问一个点，则记录当前时间 startTime=clock，并尝试从这个点出发，看能否找到环。如果找到了一个之前访问过的点 x，且之前访问 x 的时间不早于 startTime，则说明我们找到了一个新的环，此时的环长就是前后两次访问 x的时间差，即clock−time[x]。

取所有环长的最大值作为答案。若没有找到环，则返回 -1

作者：endlesscheng
链接：https://leetcode.cn/problems/longest-cycle-in-a-graph/solution/nei-xiang-ji-huan-shu-zhao-huan-li-yong-pmqmr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

当访问到一个已经被访问过的点的时候，有两种情况，有可能是找到了环，也有可能是之前被被人访问过了。需要分情况讨论。

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        # 时间戳，这个方法太帅了
        n = len(edges)
        time = [0] * len(edges)
        clock, ans = 1, -1
        for i in range(n):
            # 访问过了
            if time[i]: continue
            # 否则
            start_time = clock
            x = i 
            # 开始找环
            while x != -1:
                if time[x]: # 如果召唤的过程中发现了访问过的
                    # 判断是找到了一个环呢，还是说访问了之前被访问过的
                    if time[x] >= start_time: # 找到了一个环
                        ans = max(ans, clock - time[x])
                    break
                # 否则，继续往下走
                time[x] = clock
                clock += 1
                x = edges[x]
        
        return ans

class Solution {
    
public:
    int longestCycle(vector<int>& p) {
    
        int n = p.size();
        int time[n]; // 草，这里忘了全部初始化为0了
        memset(time, 0, sizeof(time));
        int res = -1;
        int clock = 1;

        for(int i = 0; i < n; i ++)
        {
    
            if(time[i]) continue;
            // 开始找环
            int start_time = clock;
            int x = i;
            while(x != -1)
            {
    
                if(time[x])
                {
    
                    if(time[x] >= start_time)
                    {
    
                        res = max(res, clock - time[x]);  
                    }
                    break;      
                }
                // 否则，继续往下走
                time[x] = clock;
                clock ++;
                x = p[x];
            }
                
        }

        return res;
    }
};

y总的写法：
开始：https://www.bilibili.com/video/BV11S4y1x7iM?spm_id_from=333.999.0.0&vd_source=dc27dfeb3c137279f3aaf4ac12fd6796&t=2059.6

class Solution {
    
public:
    // 这几个都是全局变量
    vector<int> p;
    vector<bool> st; // 表示是否被访问过
    vector<int> in_stk; // 表示是否在栈中
    int ans = -1;

    void dfs(int u, int depth)
    {
    
        st[u] = true;
        in_stk[u] = depth;

        int j = p[u]; //下一个点
        if(j != -1)
        {
    
            if(!st[j])
            {
    
                dfs(j, depth + 1);
            }else if(in_stk[j])
            {
    
                ans = max(ans, depth + 1 - in_stk[j]);
            }
        }
        
        // 恢复现场，因为u用完了
        in_stk[u] = 0;
    }

    int longestCycle(vector<int>& p) {
    
        // 如何让p变成全局变量？
        this->p = p;
        int n = p.size();
        // 这两个初始化的时候默认为0
        st = vector<bool>(n);
        in_stk = vector<int>(n);

        for(int i = 0; i < n; i ++)
            if(!st[i]) 
                // 从i开始，搜过的长度为1
                dfs(i, 1);
        
        return ans;
    }
};