What is the key pattern for solving the Longest Cycle in a Graph problem?

The key pattern involves using graph indegree and topological ordering to detect cycles in a directed graph.

How does Depth-First Search (DFS) work for this problem?

DFS works by visiting nodes and backtracking when a cycle is found, marking nodes as visited to avoid revisiting them.

What is the time complexity for solving this problem?

The time complexity is O(n), where n is the number of nodes in the graph, as each node is visited once during traversal.

Can this problem be solved using Breadth-First Search (BFS)?

Yes, BFS can also be used by exploring nodes level by level, checking for cycles as nodes are revisited.

What should I do if no cycle exists in the graph?

If no cycle is found, the answer should be -1, indicating the absence of a cycle.

#2360

Hard

auto_awesome图·搜索

LeetCode 题解工作台

图中的最长环

给你一个 n 个节点的有向图，节点编号为 0 到 n - 1 ，其中每个节点至多有一条出边。图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。请你返回图中的最…

深度优先搜索广度优先搜索图拓扑排序

题目描述

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

lightbulb

解题思路

方法一：遍历出发点

我们可以遍历 $[0,..,n-1]$ 范围内的每个节点，如果该节点未被访问过，则从该节点出发，搜索邻边节点，直到遇到环或者遇到已经访问过的节点。如果遇到环，则更新答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点数。

相似题目：

2127. 参加会议的最多员工数

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        vis = [False] * n
        ans = -1
        for i in range(n):
            if vis[i]:
                continue
            j = i
            cycle = []
            while j != -1 and not vis[j]:
                vis[j] = True
                cycle.append(j)
                j = edges[j]
            if j == -1:
                continue
            m = len(cycle)
            k = next((k for k in range(m) if cycle[k] == j), inf)
            ans = max(ans, m - k)
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the traversal algorithm used. For DFS or BFS, it is O(n), where n is the number of nodes. Space complexity depends on the space used for marking visited nodes and storing cycle data, which is also O(n).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate's understanding of graph traversal techniques like DFS or BFS and their ability to detect cycles.
question_mark
How well the candidate can optimize space and time complexity while dealing with graph traversal.
question_mark
Ability to connect the graph indegree and topological ordering patterns to detect cycles efficiently.

warning

常见陷阱

外企场景

error
Confusing cycle detection with simple path finding.
error
Overlooking the need for revisiting nodes that are part of a potential cycle.
error
Incorrectly handling the case where no cycle exists and returning invalid results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Graphs with multiple cycles or no cycles.
arrow_right_alt
Graphs where some nodes point to themselves.
arrow_right_alt
Optimizing for graphs with extremely large sizes, requiring efficient traversal.

help

常见问题

外企场景

继续练习

#2328 网格图中递增路径的数目 #2192 有向无环图中一个节点的所有祖先 #1462 课程表 IV