Longest Loop in a Conveyor Network
Solve this ProblemA conveyor network has n stations; every station has at most one outgoing conveyor (so its adjacency list is empty or holds a single station). A loop is a route along the conveyors that returns to its starting station. Find the length of the longest loop, or -1 if the network has none.
Because each station has at most one exit, walks never branch, which makes it possible to measure a loop by comparing step numbers instead of exploring the whole graph.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 10 stations numbered 0 … n-1; graph[u] is the adjacency list of a directed graph in which every station has at most one outgoing conveyor: graph[u] is either empty or holds exactly one station - ◆
A conveyor from a station to itself is allowed (a loop of length 1) - ◆
A loop is a route that follows the conveyors and returns to its starting station; its length is the number of conveyors used - ◆
Return the length of the longest loop, or -1 if there is none
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Walk Up to n Steps From Every Station
BruteEvery station has at most one conveyor to follow, so a walk from any station is a single path. For each station, follow the conveyors for up to n steps; if you get back to the station you started from, the number of steps taken is the length of a loop through it. Keep the largest such number. A walk that never returns (it ends or enters a different loop) contributes nothing. n stations times n steps: O(n²).
O(n²)O(1)1class Solution {
2 public int longestLoop(int[][] graph) {
3 int n = graph.length;
4 int best = -1;
5 for (int start = 0; start < n; start++) {
6 int cur = start;
7 for (int steps = 1; steps <= n; steps++) {
8 if (graph[cur].length == 0) break;
9 cur = graph[cur][0];
10 if (cur == start) {
11 best = Math.max(best, steps);
12 break;
13 }
14 }
15 }
16 return best;
17 }
18}Optimal — Walk Once and Use Step Numbers to Measure the Loop
OptimalWalk from an unvisited station and give each station the step number at which it is entered (time[]), also remembering which walk owns it (owner[]). The walk stops at a station that is already stamped, or at the end of the road. If the stopping station is stamped by THIS walk, we have gone around a loop, and its length is the current step number minus the step at which that station was first entered. Stations stamped by earlier walks were already accounted for. Every station is stamped once: O(n).
O(n)O(n)1class Solution {
2 public int longestLoop(int[][] graph) {
3 int n = graph.length;
4 int[] time = new int[n];
5 int[] owner = new int[n];
6 Arrays.fill(owner, -1);
7 int best = -1;
8 for (int start = 0; start < n; start++) {
9 if (time[start] != 0) continue;
10 int t = 1;
11 int cur = start;
12 while (cur != -1 && time[cur] == 0) {
13 time[cur] = t;
14 owner[cur] = start;
15 t++;
16 cur = graph[cur].length == 0 ? -1 : graph[cur][0];
17 }
18 if (cur != -1 && owner[cur] == start) {
19 best = Math.max(best, t - time[cur]);
20 }
21 }
22 return best;
23 }
24}