Skip to content
Katabench
Try free

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] == -1 means node i has no outgoing edge.
  • Otherwise, next[i] is the valid index of the node reached from i.

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 performance bar

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

C#
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.

C# coding challenges →

What it practices

Depth-first search
Recurse or use an explicit stack to explore connected regions, paths and components.

Related katas