图中的最长环

难度:

标签:

题目描述

给你一个 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 <= 10⁵
-1 <= edges[i] < n
edges[i] != i

代码结果

运行时间: 134 ms, 内存: 27.8 MB

// Problem: Given a directed graph represented by an array edges where each node has at most one outgoing edge,
// find the length of the longest cycle in the graph. Return -1 if no cycle exists.

// Java solution using Streams:
// Similar to the previous approach, but we will use Java Streams to create arrays and iterate through the nodes.

import java.util.stream.IntStream;

public class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length;
        boolean[] visited = new boolean[n];
        int[] distance = IntStream.range(0, n).map(i -> -1).toArray();
        final int[] longest = {-1};

        IntStream.range(0, n).forEach(i -> {
            if (!visited[i]) {
                int current = i, dist = 0;
                while (current != -1 && !visited[current]) {
                    visited[current] = true;
                    distance[current] = dist++;
                    current = edges[current];
                }
                if (current != -1 && visited[current] && distance[current] >= 0) {
                    longest[0] = Math.max(longest[0], dist - distance[current]);
                }
            }
        });

        return longest[0];
    }
}

解释

方法:

题解使用了一个遍历标记法来检测并记录图中的环。首先，定义一个数组 times 来存储每个节点第一次被访问的时间。遍历图中的每个节点，如果节点已经被访问过，则跳过。对于未访问的节点，从该节点出发，遍历其路径。如果遇到已经访问过的节点，检查这个节点的访问时间是否在当前搜索开始之后，如果是，说明找到了一个环，并用当前时间减去该节点的访问时间来计算环的长度，更新最大环长。若遇到的已访问节点不在当前搜索开始之后，表示此次搜索没有发现新的环，停止当前路径的搜索。这个过程重复直到所有节点都被检查。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

题解中提到`如果访问过当前节点`，然后检查`如果times[x] >= start_time`来判断是否形成了环。这里的逻辑是否意味着只有在当前的搜索路径中访问过的节点才能形成环？

▷

是的，这里的逻辑确实是这样的。在这种检测环的方法中，只有在当前的搜索路径中之前访问过的节点才会被考虑形成环。这是因为times数组记录了每个节点第一次被访问的时间戳，而start_time记录了当前路径搜索的开始时间。如果在搜索过程中遇到一个已经访问过的节点，并且该节点的访问时间大于等于start_time，这意味着这个节点在当前的搜索路径中被访问过，因此在这两个节点之间形成了一个环。

🦆

在处理节点i没有出边的情况（即`edges[i] == -1`）时，题解中的逻辑是如何确保不会错误地继续搜索或者错误地计算环的长度？

▷

在题解的算法中，如果一个节点i没有出边（即`edges[i] == -1`），那么在代码中`x = edges[x]`这一行将会使x变为-1。代码中的循环条件是`while x >= 0`，因此当x变为-1时，循环将自动停止，不会继续搜索或者错误地计算环的长度。这种处理方式确保了在遇到没有出边的节点时，搜索能够正确地停止。

🦆

题解算法在检测到环的情况下是如何确保及时退出当前路径搜索的？是否有可能在环被检测后仍然继续无用的遍历？

▷

题解算法通过检查节点的访问时间来确定是否形成了环，并且一旦检测到环，通过`break`语句立即退出当前的while循环，这样可以及时停止当前路径的搜索。这种方法有效地避免了在环被检测到后继续无用的遍历。一旦环的存在被确认，没有必要继续遍历当前路径中的其他节点，因为这不会发现新的环或更长的环，从而确保了算法的效率。

图中的最长环

题目描述

代码结果

解释

代码细节讲解

相关问题