当前位置：首页 > article >正文

leetcode 2360 图中最长的环题解

article 2025/4/1 2:03:22

题面

给定一个有向图，每个点出度最大为一，现在问你图中最长的环的长度是多少，如果没有环输出 -1， $\le n \le 10^5$ 。
题面

解题思路

我们直接说结论，我们从任意一个点出发，用一个数组存下来到达每一个点的最短步数，如果发现一个点之前已经被遍历过了，那么这个点一定是一个环的起点和终点，环的长度是当前的步数减去这个点的最短步数。

下面稍微证明一下，我们来看题目中给出的条件，每一个点最多只有一条出边，那么这个条件告诉了我们两件事情：

边数比较小；
图中不存在以下情况：

所以当我们遍历的时候，所有经过的点和边形成的一定是一个链型的结构。当发现有一个点重复遍历的时候，一定是返回到了链上前面的某一个点，形成了一个环，我们统计一下答案就好了。

除此之外我们要注意，题目没有保证任意两点之间可以互相到达，当我们遍历一次之后我们还要检查还有没有别的点我们没有遍历。

任意两次遍历是互不影响的，或者说一个环只可能出现在具体的一次遍历当中，所以当我们完成一次遍历的时候，直接把这次的点全部都删了就行，不然复杂度就上来了。

代码

class Solution {
public:
    int ans = -1; // 最终答案
    vector<int> dis; // 存最短步数

    void dfs(int x, int D, vector<int>& edges) // D 表示当前步数
    {
        if (dis[x] != 0) // 如果发现之前被遍历过了，说明可能存在环
        {
            if (dis[x] == -1) // -1 说明是之前的遍历，不用管
                return;
            ans = max(ans, D - dis[x]); // 否则就是存在环，记录答案
            return;
        }
        dis[x] = D; // 维护 dis
        if (edges[x] != -1)
            dfs(edges[x], D + 1, edges); // 最多只有一个出度，就不用 for 循环了
        dis[x] = -1; // 遍历完成开始回溯了，直接把这个点删掉
    }

    int longestCycle(vector<int>& edges) {
        const int N = edges.size();
        dis.resize(100005, 0); 
        for (int i = 0; i < N; i++) // 记得要遍历所有的点
            if (dis[i] == 0)
                dfs(i, 1, edges);
        return ans;
    }
};