Measure the Longest Directed Cycle in a One-Exit Graph
Company: Anduril
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
In the directed graph represented by `edges`, each node has at most one outgoing edge. `edges[i]` gives its destination, or `-1` for no edge. Return the number of nodes in the longest directed cycle. Return `-1` if no cycle exists.
```cpp
class Solution {
public:
int longestCycle(vector<int>& edges);
};
```
### Examples
**Example 1:**
```text
Input: edges = [1,2,0,-1]
Output: 3
Explanation: Nodes 0,1,2 form one directed cycle. Node 3 has no outgoing edge.
```
**Example 2:**
```text
Input: edges = [1,-1,1]
Output: -1
Explanation: Every forward walk eventually reaches node 1, whose outgoing edge is absent.
```
### Constraints
- `2 <= edges.length <= 100000`.
- `-1 <= edges[i] < n`.
- `edges[i] != i`.
### Clarifying Questions
- Do incoming branches count toward a cycle's length? No; count only the nodes on the closed directed route.
- Can edges be followed backward? No.
- Can a node point to itself? No, the constraints exclude self-edges.
- What is returned for an acyclic graph? `-1`.
```hint Check the boundary
Separate a path that enters a cycle from the nodes actually on that cycle.
```
Overview: Find the longest directed cycle in a graph with at most one outgoing edge per node, returning -1 when no cycle exists.