Show problems as
Classic problem #2360HardDepth-First SearchBreadth-First SearchGraph TheoryTopological SortKosaraju's AlgorithmTarjan's SCC Algorithm

Longest Cycle in a Graph

Real-world version: Longest Loop in a Relay Network
Tracked in this browser only
Read Longest Cycle in a Graph on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstCycle Detection · Graphs, animated step by step

A packet network has stations numbered 0 to n - 1. Each station hands every packet it receives to at most one other station: forward[i] is the station that station i hands to, and forward[i] = -1 means station i keeps what it receives and hands on nothing. No station hands to itself.

A loop is a list of distinct stations s[0], s[1], ..., s[L-1] with L >= 2 where each station hands to the next one, forward[s[j]] = s[j + 1] for every j below L - 1, and the last hands back to the first, forward[s[L-1]] = s[0]. The length of that loop is L, the number of stations on it.

Return the length of the longest loop in the network, or -1 if no loop exists.

Examples

Example 1

Input
forward = [1, 0, 3, 4, 2, 6, -1]
Output
3

Stations `2, 3, 4` hand on in a ring, which is a loop of three. Stations `0` and `1` hand to each other, a loop of two. Station `5` hands to `6`, which hands on nothing.

Example 2

Input
forward = [1, 2, 3, 4, 5, 3]
Output
3

Stations `3, 4, 5` form a loop of three. Stations `0, 1, 2` lead into it but nothing hands back to them, so they are on no loop.

Example 3

Input
forward = [1, 2, 3, 4, -1]
Output
-1

Every packet travels forward to station `4` and stops there. No station is ever handed back to, so there is no loop and the sentinel is returned.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_relay_loop(forward: list[int]) -> int:
Java
public int longestRelayLoop(int[] forward)

More on the same topics