Longest Cycle in a Graph

Naive Approach (Brute Force)

The most straightforward approach is to iterate through each node and perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to detect cycles starting from that node. For each node, we explore the path until we either find a cycle or reach a dead end (node with no outgoing edge).

Algorithm:

1. Iterate through each node from 0 to n-1.
2. For each node, start a DFS/BFS.
3. Keep track of visited nodes in the current path.
4. If we encounter a node already visited in the current path, a cycle is detected. Calculate the length of the cycle.
5. Keep track of the maximum cycle length found so far.
6. If no cycle is found, return -1.

Code (Python):

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

    for start_node in range(n):
        visited = [False] * n
        path = []
        node = start_node

        while node != -1 and not visited[node]:
            visited[node] = True
            path.append(node)
            node = edges[node]

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

    return max_cycle_length

Complexity Analysis:

• Time Complexity: O(N^2) in the worst case. For each node, we might potentially visit all other nodes.
• Space Complexity: O(N) for the visited array and path.

Optimal Approach

The optimal solution leverages the fact that each node has at most one outgoing edge. We can use a similar DFS approach, but with a more efficient way of tracking visited nodes and calculating cycle lengths.

Algorithm:

1. Initialize visited array to keep track of visited nodes.
2. Iterate through each node.
3. If the node hasn't been visited, start a DFS.
4. During DFS, keep track of the distance from the starting node.
5. If we encounter a node already visited in the current DFS path, we have found a cycle. The length of the cycle is the difference between the current distance and the distance when we first visited the node.
6. If we encounter a node that has been visited in a previous DFS (i.e., visited[node] == True but dist[node] is still -1), we stop the traversal along that path because it cannot form a new, longer cycle.
7. Keep track of the maximum cycle length.

Code (Python):

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

    for start_node in range(n):
        if not visited[start_node]:
            dist = [-1] * n  # Distance from the start node for the current DFS
            dist[start_node] = 0
            node = start_node

            while node != -1 and not visited[node]:
                visited[node] = True
                next_node = edges[node]

                if next_node != -1 and dist[next_node] == -1:
                    dist[next_node] = dist[node] + 1

                node = next_node

            if node != -1 and dist[node] != -1:
                cycle_length = dist[start_node] - dist[node] +1 if dist[node] < dist[start_node] else dist[node] - dist[start_node] + 1
                max_cycle_length = max(max_cycle_length, cycle_length)

    return max_cycle_length

Complexity Analysis:

• Time Complexity: O(N). Each node is visited at most once.
• Space Complexity: O(N) for the visited and dist arrays.

Edge Cases:

• No cycles: If the graph contains no cycles, the algorithm will correctly return -1.
• Self-loops: The problem statement specifies edges[i] != i, so self-loops are not possible.
• Disconnected graph: The algorithm correctly handles disconnected graphs because it iterates through each node and starts a DFS if the node hasn't been visited yet.
• Multiple cycles: The algorithm finds the longest cycle among all cycles in the graph.