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]. If there is no outgoing edge from node i, then edges[i] == -1.
Return the length of the longest cycle in the graph. If no cycle exists, return -1.
A cycle is a path that starts and ends at the same node.
Example 1:
Input: edges = [3,3,4,2,3] Output: 3 Explanation: The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2. The length of this cycle is 3, so 3 is returned.
Example 2:
Input: edges = [2,-1,3,1] Output: -1 Explanation: There are no cycles in this graph.
Constraints:
n == edges.length2 <= n <= 105-1 <= edges[i] < nedges[i] != iThis approach involves using Depth First Search (DFS) to traverse the graph nodes by starting at each unvisited node. As we explore, we track the nodes in the current path to detect cycles. Whenever we reach a previously visited node that is part of the current path, a cycle is detected, and its length is computed. We keep track of the longest cycle found during the traversal.
The C solution utilizes DFS to detect cycles. Using arrays for tracking visited nodes and recursion stack during traversal, we calculate the cycle length whenever a cycle is detected by re-entering a node part of the current path.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes. We visit each node and edge once.
Space Complexity: O(n), required for the recursion stack and visited nodes array.
Largest Color Value in a Directed Graph - Leetcode 1857 - Python • NeetCodeIO • 22,081 views views
Watch 9 more video solutions →Practice Longest Cycle in a Graph with our built-in code editor and test cases.
Practice on FleetCode