Longest Cycle in a Graph

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.

For example:

edges = [3,3,4,2,3] should return 3 The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2. The length of this cycle is 3, so 3 is returned.

edges = [2,-1,3,1] should return -1 There are no cycles in this graph.

Constraints:

• n == edges.length
• 2 <= n <= 10^5
• -1 <= edges[i] < n
• edges[i] != i

## Longest Cycle in a Directed Graph

This problem asks us to find the longest cycle in a directed graph where each node has at most one outgoing edge. If no cycle exists, we should return -1.

### Naive Solution (Brute Force)

A brute-force approach would be to start from each node and perform a Depth-First Search (DFS) to detect cycles. For each node, we track the visited nodes and the current path length. If we encounter a node already in the current path, we have found a cycle and update the maximum cycle length.

```python
def longestCycle_brute_force(edges):
    n = len(edges)
    max_cycle_length = -1

    for start_node in range(n):
        visited = [False] * n
        path = []
        
        def dfs(node):
            nonlocal max_cycle_length
            if node == -1:
                return
            
            if visited[node]:
                return

            if node in path:
                cycle_length = len(path) - path.index(node)
                max_cycle_length = max(max_cycle_length, cycle_length)
                return

            visited[node] = True
            path.append(node)

            dfs(edges[node])
            path.pop()

        dfs(start_node)
    
    return max_cycle_length

Time Complexity: O(N^2) in the worst case, where N is the number of nodes. For each node, we potentially traverse all other nodes.

Space Complexity: O(N) due to the visited array and the path list.

Optimal Solution

A more efficient solution involves tracking the distance from the starting node for each path. We use a visited array to mark nodes visited during the DFS and a dist array to track the distance from the starting node. When we encounter a node already in the current path, we can calculate the cycle length as the difference between the current distance and the distance when we first visited that node.

def longestCycle(edges):
    n = len(edges)
    max_cycle_length = -1
    visited = [False] * n

    for start_node in range(n):
        if visited[start_node]:
            continue

        dist = [-1] * n
        curr = start_node
        count = 0

        while curr != -1 and not visited[curr]:
            visited[curr] = True
            dist[curr] = count
            count += 1
            curr = edges[curr]

        if curr != -1 and dist[curr] != -1:
            cycle_length = count - dist[curr]
            max_cycle_length = max(max_cycle_length, cycle_length)

    return max_cycle_length

Explanation:

1. Initialization:

   • max_cycle_length is initialized to -1.
   • visited array to keep track of visited nodes during DFS.

2. Outer Loop:

   • Iterate through each node as a potential starting point for a cycle.
   • If a node is already visited, skip it.

3. Inner Loop (DFS):

   • dist array to store the distance from the starting node.
   • curr represents the current node.
   • count represents the current distance from the starting node.
   • While the current node is valid (not -1) and not yet visited:
     • Mark the current node as visited.
     • Store the distance from the start node.
     • Move to the next node according to the edges array.

4. Cycle Detection:

   • After the inner loop, if curr is not -1 and dist[curr] is not -1, it indicates a cycle is found.
   • Calculate the cycle length as count - dist[curr]. This is the difference between the current distance and the distance when we first visited that node in the current path.
   • Update max_cycle_length if a longer cycle is found.

5. Return Result:

   • Return the maximum cycle length found.

Big(O) Runtime Analysis

• The outer loop iterates through each node, which takes O(N) time.
• The inner loop (DFS) visits each node at most once, also taking O(N) time in the worst case.
• Therefore, the overall time complexity is O(N).

Big(O) Space Usage Analysis

• The visited array takes O(N) space.
• The dist array takes O(N) space.
• Thus, the overall space complexity is O(N).

Edge Cases

1. Empty Graph: If the edges array is empty, there are no cycles, so the function should return -1.
2. No Cycles: If the graph does not contain any cycles, the function should return -1.
3. Self-Loops: If edges[i] == i for some node i, there is a self-loop of length 1. This needs to be correctly identified and handled. However, the problem states edges[i] != i so this will not happen.
4. Disconnected Components: The graph may consist of multiple disconnected components. The algorithm must consider all components to find the longest cycle.
5. Large Graph: For a very large graph, the algorithm's memory usage could become a concern. However, since the space complexity is linear, it should be manageable for the given constraint 2 <= n <= 10^5.