A satellite relay network is stored as nodes numbered 0 to n-1. Node 0 is the head. Each node has exactly one outgoing link, given as a next index (or -1 if it links to nothing). Starting at the head and repeatedly following next, you either eventually reach a node whose link is -1 (no cycle), or you loop forever inside a cycle. Report the number of distinct nodes that make up that cycle, or 0 if the path from the head terminates without cycling.
Line 1: an integer n, the number of nodes.
Line 2: n space-separated integers, the node values (empty line when n is 0). These do not affect the answer but describe the nodes.
Line 3: n space-separated integers, where the i-th is next[i] in the range [-1, n-1] (empty line when n is 0).
A single integer: the number of nodes in the cycle reachable from the head, or 0 if there is no cycle.
Example 1
Input
5 1 2 3 4 5 1 2 3 4 2
Expected
3
Explanation
From head 0 the path is 0->1->2->3->4->2, so nodes 2,3,4 form a cycle of length 3.
Example 2
Input
4 1 2 3 4 1 2 3 -1
Expected
0
Explanation
The path 0->1->2->3 ends at a null link (next[3] = -1), so there is no cycle: 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →