Follow One-Way Links to the Endpoint Node or the Last Node Before a Loop Closes

A simple network is made of nodes joined by one-way links. Each node links to at most one other node, in a single forward direction. Starting from a given node and following the links, find the endpoint of the network: the last node the walk reaches. If the walk runs into a loop instead, return the last node traversed before the loop closes.

Function Signature

def compute(start_node_id: int, from_ids: list[int], to_ids: list[int]) -> int:

from_ids and to_ids have the same length and describe the links: for every i, node from_ids[i] links to node to_ids[i].

Rules

• The walk starts at start_node_id, which counts as visited.
• If the current node has no outgoing link (its id does not appear in from_ids), the walk ends and the current node is the answer. In particular, if start_node_id has no outgoing link, the answer is start_node_id.
• Otherwise, look at the node the current node links to. If that target has not been visited yet, the walk moves to it and marks it visited.
• If the target has already been visited, following the link would close a loop. The walk ends without following it, and the answer is the current node, that is, the last node traversed before the loop closes.
• The loop does not have to contain start_node_id; the walk may pass through other nodes before it enters the loop.

Constraints

• Every node id, including start_node_id, is an integer with 1 <= id < 5000.
• Node ids are not necessarily ordered or contiguous; some ids in that range may not appear in the network at all.
• len(from_ids) == len(to_ids) and 0 <= len(from_ids) <= 4999.
• The values in from_ids are pairwise distinct, since each node has at most one outgoing link. Several nodes may link to the same node.
• from_ids[i] != to_ids[i] for every i: no node links directly to itself.

Examples

Example 1

Input: start_node_id = 2, from_ids = [1, 7, 3, 4, 2, 6, 9], to_ids = [3, 3, 4, 6, 6, 9, 5]
Output: 5

The walk is 2 -> 6 -> 9 -> 5. Node 5 has no outgoing link, so it is the endpoint. Every other starting node in this network also ends at 5, for example 1 -> 3 -> 4 -> 6 -> 9 -> 5. Node 8 does not exist in this network.

Example 2

Input: start_node_id = 1, from_ids = [1, 2, 3], to_ids = [2, 3, 1]
Output: 3

The walk visits 1 -> 2 -> 3. The link from 3 leads back to 1, which was already visited, so the loop closes there and the answer is 3.

Example 3

Input: start_node_id = 7, from_ids = [7, 4, 5, 6], to_ids = [4, 5, 6, 4]
Output: 6

The walk visits 7 -> 4 -> 5 -> 6. The link from 6 leads to 4, which was already visited, so the answer is 6. Node 7 leads into the loop but is not part of it.