Solution: Longest Cycle in a Graph

Statement

You are given a directed graph with n nodes, labeled from 0 to n - 1. Each node in the graph has at most one outgoing edge.

The graph is described using a 0-indexed integer array edges of length n, where:

• edges[i] represents a directed edge from node i to node edges[i].

• If node i has no outgoing edge, edges[i] == -1.

Your task is to find longest cycle length in the graph. If no cycle exists, return -1.

Note: A cycle is defined as a path that starts and ends at the same node, following the direction of the edges.

Constraints:

• n $==$ edges.length

• $2 \leq$ n $\leq 10^{5}$

• $-1 \leq$ edges[i] $\leq$ n

• edges[i] $\neq$i

Solution

The essence of this solution lies in identifying and measuring the length of cycles in a directed graph where each node has at most one outgoing edge. We can think of this problem as exploring paths starting from each node until we either revisit a node, indicating a cycle, or reach a node without an outgoing edge. It uses the graphs pattern, with an iterative traversal approach. The key idea is to traverse paths in the graph while keeping track of the order in which nodes are visited using step counters. This helps us detect if we revisit a node within the same traversal, indicating a cycle. The cycle’s length is then calculated based on the step difference between the current node and when it was first visited in this path. Across all traversals, the algorithm records the length of the longest cycle found.

Now, let’s look at the steps of the solution:

1. Create a list visited_time of size n initialized with -1 to track when each node is globally visited.

2. Initialize time = 0 as a step counter and max_cycle = -1 to store the longest cycle length found.

3. Loop through all nodes and begin a new traversal for each unvisited node.

4. Initialize a dictionary node_to_time to record the visit step of each node during the current traversal.

5. Traverse the graph by following outgoing edges while the current node is valid and unvisited.

6. For every node visited in this traversal:

   1. Store the current time in both visited_time and node_to_time for the current node.

   2. Increment time to prepare for the next step.

   3. Move to the next node using the edge: current = edges[current].

7. A cycle is detected if the next node is already in node_to_time, and its length is time - node_to_time[current].

8. Update max_cycle with the longer of its current value or the newly found cycle length.

9. After all nodes are processed, return max_cycle as a result, or -1 if no cycle was found..

This approach ensures every node is visited at most once, avoids redundant processing, and efficiently finds the longest cycle.

Let’s look at the following illustration to get a better understanding of the solution: