Longest Cycle in a Functional Graph
Hard About 40 min Free, no account needed
Find the largest directed cycle without retracing every path.
The brief
An integer array next describes a directed graph whose nodes are the indices
0..next.Length - 1. Every node has at most one outgoing edge:
next[i] == -1means nodeihas no outgoing edge.- Otherwise,
next[i]is the valid index of the node reached fromi.
Return the number of nodes in the longest directed cycle. A self-loop has
length 1. Return -1 when the graph contains no cycle, including when the
array is empty. Do not modify next.
The honest brute-force approach starts a fresh traversal from every node and uses a new set to find a repeated node. One traversal can visit most of the graph, so repeating it from every start costs O(n^2).
The hidden graphs have 200,000 nodes. One has a 100,000-node tail leading into a 100,000-node cycle; another has two disjoint 100,000-node cycles. A per-start traversal repeats billions of steps across both single-component and multi-component shapes. Process each node only a constant number of times by distinguishing a node discovered in the current traversal from one completed by an earlier traversal.
Starter code
using System;
public class Solution
{
// TODO: return the number of nodes in the longest directed cycle, or -1.
public int LongestCycle(int[] next)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Depth-first search
- Recurse or use an explicit stack to explore connected regions, paths and components.
Related katas
- Number of Islands Medium Free Count the connected patches of land in a grid.
- Flood Fill Easy Free The paint-bucket tool - including the click that changes nothing.
- Count Bounded Range Sums Hard Free Count signed subarray totals inside an inclusive band without enumerating quadratic pairs.
- Count Inversions Hard Free Count every out-of-order pair without examining every pair.