Overview

This problem asks us to find the length of the loop that ultimately forms when following the chain of messages starting from each student. We utilize the structure of a “Functional Graph,” where each node has exactly one outgoing edge, to efficiently determine the size of the cycle that each node reaches.

Analysis

Understanding the Problem Structure

Each student \(i\) has exactly one designated recipient \(T_i\). This forms a graph where each node has exactly one outgoing edge, known as a Functional Graph.

Functional Graphs have important properties:

• Each connected component contains exactly one cycle
• Nodes that do not belong to a cycle extend as “tails” leading toward the cycle

For example, with \(N=6\), \(T = [2, 3, 4, 2, 4, 5]\):

1 → 2 → 3 → 4 → 2 (cycle: 2→3→4→2, length 3)
5 → 4 (merges into cycle 2→3→4→2)
6 → 5 → 4 (merges into the same cycle)

Observing the Answer

Starting from student \(s\) and following \(s, T_s, T_{T_s}, \ldots\), we eventually reach a previously visited node \(v\). The length of the cycle from \(v\) back to \(v\) is the answer.

• If \(s\) is a node on a cycle: Starting from \(s\), we traverse the cycle and return to \(s\) itself. The answer is the length of that cycle.
• If \(s\) is a tail node: Following the edges, we reach the cycle’s entry point \(v\), go around, and return to \(v\). The answer is the length of the reached cycle.

In other words, regardless of the starting node, the answer is the size of the cycle that the node ultimately reaches.

Problem with the Naive Approach

If we naively follow edges from each node, it takes up to \(O(N)\) steps per node, resulting in \(O(N^2)\) overall, which will TLE.

Algorithm

Step 1: Detect All Cycles and Compute Their Sizes

We manage each node with a color (\(0\): unvisited, \(1\): in progress, \(2\): finalized).

1. Starting from an unvisited node \(s\), follow edges while recording the path
2. If we reach a node with color \(1\) (in progress), we have discovered a new cycle. The portion of the path from that node to the end forms the cycle
3. If we reach a node with color \(2\) (finalized), all nodes on the current path are tails

Step 2: Identify the Reached Cycle for Each Tail Node

Nodes on cycles already have their cycle IDs determined. For tail nodes, we follow edges until reaching a node whose cycle ID is known, then record the same cycle ID for all nodes along the path (path compression).

Finally, we output \(ans[i] = \) the size of the cycle that node \(i\) reaches.

Complexity

• Time complexity: \(O(N)\) — each node is visited only a constant number of times (processed at most once in each of Step 1 and Step 2)
• Space complexity: \(O(N)\) — for the color array, cycle ID array, path recording array, etc.

Implementation Notes

• Iterative processing instead of recursion: Since \(N\) can be as large as \(2 \times 10^5\), recursion risks stack overflow. Use while loops to follow paths.

• Three-state management using colors: By using three colors — “unvisited,” “in progress,” and “finalized” — we can precisely identify the starting point of cycles.

• Path compression: When processing tail nodes in Step 2, by assigning the cycle ID to all nodes along the traversed path at once, we prevent redundant traversals of the same nodes.

  Source Code

import sys
from sys import setrecursionlimit

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    T = [int(input_data[i+1]) - 1 for i in range(N)]
    
    # For each node, we need to find which cycle it eventually reaches, and the size of that cycle.
    # Since each node has exactly one outgoing edge (functional graph), the structure is
    # a set of connected components each with exactly one cycle (rho-shaped).
    
    # Step 1: Find all cycles and their sizes.
    # We use a coloring approach:
    # 0 = unvisited, 1 = in progress, 2 = done
    
    color = [0] * N
    cycle_id = [-1] * N  # which cycle does this node belong to (if on a cycle)
    cycle_sizes = []  # size of each cycle
    
    # For nodes on a cycle, cycle_id[node] = index into cycle_sizes
    # For nodes not on a cycle (tails), cycle_id remains -1
    
    for s in range(N):
        if color[s] != 0:
            continue
        # Trace the path from s
        path = []
        node = s
        while color[node] == 0:
            color[node] = 1
            path.append(node)
            node = T[node]
        
        if color[node] == 1:
            # We found a new cycle. Find where the cycle starts in path.
            cycle_start = node
            idx = len(path) - 1
            while path[idx] != cycle_start:
                idx -= 1
            cycle_len = len(path) - idx
            cid = len(cycle_sizes)
            cycle_sizes.append(cycle_len)
            for j in range(idx, len(path)):
                cycle_id[path[j]] = cid
                color[path[j]] = 2
            # Mark tail nodes as done
            for j in range(idx):
                color[path[j]] = 2
        else:
            # color[node] == 2, all nodes in path are tails leading to already processed component
            for j in range(len(path)):
                color[path[j]] = 2
    
    # Step 2: For each node, find which cycle it reaches and the cycle size.
    # Nodes on a cycle: answer when starting from them = cycle size (they are on the cycle, 
    #   and following from them leads around the cycle back to themselves).
    # Wait, actually no. The problem says: start from s, follow the chain, and when you 
    # revisit a node v, the cycle from v back to v is the answer.
    # If s is on a cycle of size L, then starting from s, after L steps you return to s. Answer = L.
    # If s is a tail node, following from s eventually enters the cycle at some node v, 
    #   and then goes around the cycle back to v. Answer = cycle size.
    # So actually the answer for every node is just the size of the cycle it eventually reaches!
    
    # We need to find for each tail node, which cycle it reaches.
    # We can do this by following pointers until we hit a node with cycle_id != -1.
    # To avoid repeated work, we memoize.
    
    ans = [0] * N
    
    # For nodes on a cycle, answer is their cycle size
    for i in range(N):
        if cycle_id[i] != -1:
            ans[i] = cycle_sizes[cycle_id[i]]
    
    # For tail nodes, follow until we find a node with known answer
    # Use iterative path compression
    reach_cycle = [-1] * N  # which cycle each node reaches
    for i in range(N):
        if cycle_id[i] != -1:
            reach_cycle[i] = cycle_id[i]
    
    for i in range(N):
        if reach_cycle[i] != -1:
            continue
        # Trace from i
        path = []
        node = i
        while reach_cycle[node] == -1:
            path.append(node)
            node = T[node]
        cid = reach_cycle[node]
        for p in path:
            reach_cycle[p] = cid
            ans[p] = cycle_sizes[cid]
    
    sys.stdout.write(' '.join(map(str, ans)) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.