HardNo. 2360
Longest Cycle in a Graph — LeetCode 2360 Python Solution
- Pattern
- Topological Sort
- Topics
- Depth-First Search, Breadth-First Search, Graph, Topological Sort
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge. The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i].
Example
- Input
- edges = [3,3,4,2,3]
- Output
- 3
- Explanation
- The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2.
Python solution
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 ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the number of nodes
Pattern: Topological Sort
Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 2360. Longest Cycle in a Graph is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.
The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0207 | Course Schedule | Medium |
| 0210 | Course Schedule II | Medium |
| 0310 | Minimum Height Trees | Medium |
| 0802 | Find Eventual Safe States | Medium |
| 1203 | Sort Items by Groups Respecting Dependencies | Hard |
| 1462 | Course Schedule IV | Medium |
Frequently asked questions
- How hard is LeetCode 2360. Longest Cycle in a Graph?
LeetCode 2360. Longest Cycle in a Graph is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2360. Longest Cycle in a Graph?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2360. Longest Cycle in a Graph?
The Python solution on this page uses O(n), where n is the number of nodes auxiliary space.
- What topics does LeetCode 2360. Longest Cycle in a Graph cover?
LeetCode 2360. Longest Cycle in a Graph is tagged Depth-First Search, Breadth-First Search, Graph and Topological Sort on LeetCode.