Hard

题目描述

给你一个有 n 个节点的有向图，节点编号从 0 到 n - 1，其中每个节点 至多 有一条出边。

图用一个长度为 n 的给定数组 edges 表示，其中 edges[i] 表示存在一条从节点 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^5
  • -1 <= edges[i] < n
  • edges[i] != i

解题思路

这道题需要找到有向图中的最长环。由于每个节点最多有一条出边，这种图的结构相对简单，我们可以利用这个特性来解决问题。

核心思路：

由于每个节点最多有一条出边，这意味着：

  1. 每个节点最多只能属于一个环
  2. 从任何节点开始，沿着出边走，要么遇到环，要么走到没有出边的节点

算法步骤：

  1. 使用访问状态数组来标记节点的访问状态
  2. 对每个未访问的节点，从它开始进行DFS遍历
  3. 在遍历过程中，如果遇到正在当前路径中的节点，说明找到了环
  4. 计算环的长度，并更新最大环长度
  5. 将路径上所有节点标记为已访问，避免重复计算

优化要点：

  • 使用三种状态：未访问(0)、当前路径中(1)、已完全处理(2)
  • 当前路径中的节点如果再次遇到，说明形成了环
  • 已完全处理的节点不需要再次遍历

时间复杂度为O(n)，因为每个节点最多被访问一次。

代码实现

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        vector<int> state(n, 0); // 0: unvisited, 1: in current path, 2: visited
        int maxCycle = -1;
        
        for (int i = 0; i < n; i++) {
            if (state[i] == 0) {
                unordered_map<int, int> pathIndex;
                int curr = i, index = 0;
                
                while (curr != -1 && state[curr] == 0) {
                    pathIndex[curr] = index++;
                    state[curr] = 1;
                    curr = edges[curr];
                }
                
                if (curr != -1 && state[curr] == 1) {
                    maxCycle = max(maxCycle, index - pathIndex[curr]);
                }
                
                for (auto& [node, _] : pathIndex) {
                    state[node] = 2;
                }
            }
        }
        
        return maxCycle;
    }
};

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        state = [0] * n  # 0: unvisited, 1: in current path, 2: visited
        max_cycle = -1
        
        for i in range(n):
            if state[i] == 0:
                path_index = {}
                curr = i
                index = 0
                
                while curr != -1 and state[curr] == 0:
                    path_index[curr] = index
                    index += 1
                    state[curr] = 1
                    curr = edges[curr]
                
                if curr != -1 and state[curr] == 1:
                    max_cycle = max(max_cycle, index - path_index[curr])
                
                for node in path_index:
                    state[node] = 2
        
        return max_cycle

public class Solution {
    public int LongestCycle(int[] edges) {
        int n = edges.Length;
        int[] state = new int[n]; // 0: unvisited, 1: in current path, 2: visited
        int maxCycle = -1;
        
        for (int i = 0; i < n; i++) {
            if (state[i] == 0) {
                Dictionary<int, int> pathIndex = new Dictionary<int, int>();
                int curr = i, index = 0;
                
                while (curr != -1 && state[curr] == 0) {
                    pathIndex[curr] = index++;
                    state[curr] = 1;
                    curr = edges[curr];
                }
                
                if (curr != -1 && state[curr] == 1) {
                    maxCycle = Math.Max(maxCycle, index - pathIndex[curr]);
                }
                
                foreach (var node in pathIndex.Keys) {
                    state[node] = 2;
                }
            }
        }
        
        return maxCycle;
    }
}

var longestCycle = function(edges) {
    const n = edges.length;
    const state = new Array(n).fill(0); // 0: unvisited, 1: in current path, 2: visited
    let maxCycle = -1;
    
    for (let i = 0; i < n; i++) {
        if (state[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个节点最多被访问一次，每条边最多被遍历一次
空间复杂度O(n)需要状态数组和哈希表存储路径索引

相关题目