Solution Explanation: Finding the Longest Cycle in a Directed Graph

This problem involves finding the longest cycle in a directed graph where each node has at most one outgoing edge. The graph is represented as an array edges where edges[i] indicates the node that node i points to. If edges[i] == -1, node i has no outgoing edge.

The solution uses Depth-First Search (DFS) to explore the graph and identify cycles. The key idea is to track visited nodes during the traversal. If we encounter a node that has already been visited in the current path, we've found a cycle.

Algorithm:

1. Initialization: Create a visited array to keep track of visited nodes. Initialize ans (the length of the longest cycle) to -1.

2. Iterate through nodes: Iterate through each node i in the graph.

3. DFS Traversal: If node i hasn't been visited:

   • Start a DFS traversal from node i.
   • Maintain a cycle list to store the nodes visited during the current path.
   • Mark each visited node in visited as true.
   • Continue the traversal until one of the following happens:
     • We reach a node with no outgoing edge (edges[j] == -1). In this case, the current path doesn't contain a cycle, so we move to the next node.
     • We encounter a node j that's already present in cycle. This indicates a cycle. We calculate the cycle length as cycle.length - k, where k is the index of the repeated node j in cycle. We update ans with the maximum cycle length found so far.

4. Return Result: After processing all nodes, return ans. If no cycle was found, ans remains -1.

Time Complexity Analysis:

The algorithm iterates through each node once (O(n)) and performs a DFS traversal for each unvisited node. In the worst case, the DFS traversal might visit all n nodes. Therefore, the overall time complexity is O(n), since each edge is visited at most once.

Space Complexity Analysis:

The algorithm uses a visited array of size n and a cycle list. In the worst case, the cycle list could contain all n nodes. Therefore, the overall space complexity is O(n).

Code Examples (Python):

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        visited = [False] * n
        ans = -1
 
        def dfs(node, path):
            nonlocal ans
            visited[node] = True
            path.append(node)
            next_node = edges[node]
            if next_node != -1:
                if visited[next_node]:
                    index = path.index(next_node)
                    ans = max(ans, len(path) - index)
                else:
                    dfs(next_node, path.copy())
            
            
 
        for i in range(n):
            if not visited[i]:
                dfs(i, [])
        return ans

This Python code directly implements the algorithm described above, utilizing recursion for the DFS traversal and keeping track of the current path using a list. The nonlocal keyword allows modifying the ans variable from within the nested function.

The other languages (Java, C++, Go, TypeScript) implement essentially the same algorithm with minor syntactic variations. The core logic of iterative node processing and DFS traversal with cycle detection remains consistent across all implementations.