Overview

This is a problem where each student has exactly one “next person to pass to,” forming a Functional Graph. For each starting point, we need to find the length of the loop (cycle) that is ultimately reached.

Analysis

Key Observations

• Each vertex (student) has exactly one outgoing edge (\(i \to T_i\)), so the graph consists of several loops and a collection of trees (chains) flowing into them.
• No matter which student you start from, if you keep following the edges, you will always enter some loop.
• The “number of message loop members” when the message stops is exactly the number of vertices in the cycle (cycle length) that is ultimately entered. The chain portion traversed before entering the loop is not counted.

Why the Naive Solution Doesn’t Work

If we simulate \(s, T_s, T_{T_s}, \dots\) while tracking visited nodes for each starting point \(s\): - A single simulation takes \(O(N)\) in the worst case - Doing this \(N\) times gives \(O(N^2)\)

This results in TLE for \(N \le 2\times 10^5\).

Solution Strategy

1. First identify only the vertices on loops and determine their cycle lengths as final answers
2. For vertices not on loops (chain parts), since each one flows into exactly one loop, propagate the answers using reverse edges

By using a “remove vertices with in-degree 0” process (topological removal), we can cleanly isolate only the loop portions.

Algorithm

1) Build Reverse Edges and In-degrees

• Add edges \(i \to T_i\)
• Count in-degrees indeg[x] (how many people pass to x)
• Build a reverse edge list rev[x] = [vertices that originally point to x] This is used later to “spread answers outward from the loops.”

2) Remove Vertices with In-degree 0 Using a Queue (Remove Non-loop Parts)

Vertices with in-degree 0 can never be part of a loop (since no one points to them, they cannot form a cycle), so they are chain-side vertices. - Enqueue all vertices with in-degree 0 - Dequeue a vertex, and decrement the in-degree of its destination to = T[v] by 1 - If that causes the in-degree to become 0, enqueue it next

After repeating this, the vertices remaining with indeg[i] > 0 are all on loops.

3) Traverse Remaining Loops to Determine Cycle Lengths

Starting from vertices where indeg[i] > 0 and the answer is not yet determined: - Follow i -> T[i] -> T[T[i]] -> ... which will always return to i, completing one loop - The number of vertices collected is the cycle length - Set ans[v] to the cycle length for each vertex on the loop

4) Propagate Loop Lengths to Chain Parts via Reverse Edges (BFS)

Since loop vertices already have determined answers, enqueue them, then: - Dequeue vertex v - For each vertex in rev[v] (vertices that originally point to v), if the answer is not yet determined, set ans[u] = ans[v] and add it to the queue

This propagates “the length of the loop ultimately entered” from the loops outward to all vertices.

Concrete Example

For example, with \(1\to2,\ 2\to3,\ 3\to2,\ 4\to3\), the loop is \((2,3)\) with length 2. - The answer for 2 and 3 is 2 - 1 enters the loop via 1→2, so the answer is 2 - 4 enters the loop via 4→3, so the answer is 2

Everyone gets 2.

Complexity

• Time complexity: \(O(N)\) (Each vertex and edge is processed only a constant number of times)
• Space complexity: \(O(N)\) (In-degree array, reverse edge list, queue, answer array)

Implementation Tips

• Since vertex numbers are \(1\sim N\), using 1-indexed arrays (with a dummy 0 at the front) reduces mistakes.

• For loop detection, rather than struggling with DFS, removing in-degree 0 vertices to isolate only loops is simpler and faster.

• Using rev (reverse edges) for propagation is crucial. With forward edges, you cannot spread “outward.”

• After determining cycle lengths, using loop vertices as initial values for BFS ensures all chain parts are filled without omission.

  Source Code

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    T = [0] + data[1:1 + N]

    indeg = [0] * (N + 1)
    rev = [[] for _ in range(N + 1)]
    for i in range(1, N + 1):
        to = T[i]
        indeg[to] += 1
        rev[to].append(i)

    q = deque(i for i in range(1, N + 1) if indeg[i] == 0)
    while q:
        v = q.popleft()
        to = T[v]
        indeg[to] -= 1
        if indeg[to] == 0:
            q.append(to)

    ans = [0] * (N + 1)

    # Assign cycle lengths to cycle nodes (nodes with indeg > 0 after pruning)
    for i in range(1, N + 1):
        if indeg[i] > 0 and ans[i] == 0:
            cycle = []
            cur = i
            while True:
                cycle.append(cur)
                cur = T[cur]
                if cur == i:
                    break
            clen = len(cycle)
            for v in cycle:
                ans[v] = clen

    # Propagate cycle lengths to non-cycle nodes via reverse edges
    q = deque(v for v in range(1, N + 1) if ans[v] > 0)
    while q:
        v = q.popleft()
        for u in rev[v]:
            if ans[u] == 0:
                ans[u] = ans[v]
                q.append(u)

    print(" ".join(map(str, ans[1:])))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.