2360-图中的最长环

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给你一个 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

本题 视频讲解 已出炉，包含思考题的讲解，欢迎点赞三连，在评论区分享你对这场周赛的看法~

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

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

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

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

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

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 edges 的长度。
  • 空间复杂度：O(n)。

思考题

如果题目要你返回最长环上的所有节点呢？（见 视频讲解 ）

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        time = [0] * len(edges)
        clock, ans = 1, -1
        for x, t in enumerate(time):
            if t: continue
            start_time = clock
            while x >= 0:
                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
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length, ans = -1;
        var time = new int[n];
        for (int i = 0, clock = 1; i < n; ++i) {
            if (time[i] > 0) continue;
            for (int x = i, startTime = clock; x >= 0; x = edges[x]) {
                if (time[x] > 0) { // 重复访问
                    if (time[x] >= startTime) // 找到了一个新的环
                        ans = Math.max(ans, clock - time[x]);
                    break;
                }
                time[x] = clock++;
            }
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestCycle(vector<int> &edges) {
        int n = edges.size(), time[n], ans = -1;
        memset(time, 0, sizeof(time));
        for (int i = 0, clock = 1; i < n; ++i) {
            if (time[i]) continue;
            for (int x = i, start_time = clock; x >= 0; x = edges[x]) {
                if (time[x]) { // 重复访问
                    if (time[x] >= start_time) // 找到了一个新的环
                        ans = max(ans, clock - time[x]);
                    break;
                }
                time[x] = clock++;
            }
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func longestCycle(edges []int) int {
	time := make([]int, len(edges))
	clock, ans := 1, -1
	for x, t := range time {
		if t > 0 {
			continue
		}
		for startTime := clock; x >= 0; x = edges[x] {
			if time[x] > 0 { // 重复访问
				if time[x] >= startTime { // 找到了一个新的环
					ans = max(ans, clock-time[x])
				}
				break
			}
			time[x] = clock
			clock++
		}
	}
	return ans
}

func max(a, b int) int { if b > a { return b }; return a }
 Comments
On this page
2360-图中的最长环