Overview

When messages are forwarded between members and members who have already read the message are not sent it again, find how many members receive the message starting from member 1.

Analysis

This problem involves tracking the chain of message forwarding starting from member \(1\) and counting how many members are visited before reaching a member who has already been visited.

Since each member \(i\) has a uniquely determined next recipient \(P_i\), the message forwarding can be thought of as a traversal on a “directed graph.” Each vertex (member) has exactly one outgoing directed edge (forwarding destination), so this type of graph is also called a “Functional Graph.”

Starting from member 1, we follow unvisited members one by one. If we reach a member who has already been visited, we stop. The number of members visited at that point is the answer.

A naive approach that searches through a list each time to check “has this member already been visited” would result in \(O(N^2)\) time complexity in the worst case, which is too slow for the constraint \(N \leq 2 \times 10^5\). Therefore, to quickly determine “whether a member has read the message,” we prepare a visited array of size \(N+1\) and record True/False at the index corresponding to each member, enabling constant-time lookups.

Algorithm

1. Read the forwarding destination \(P_i\) for each member.
2. Start from member 1 and repeat the following process:
   • If the current member has already been visited, stop.
   • Otherwise, mark that member as visited and increment the count.
   • Move to the next member (move to \(P_{\text{current}}\)).
3. Output the count.

This algorithm efficiently follows the unique path starting from member 1.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Since each member is visited at most once, the number of steps in the while loop is at most \(N\). Also, the visited array has size \(N+1\), so the space complexity is \(O(N)\) as well.

Implementation Notes

• Member numbers are 1-indexed, so when accessing arrays, you need to subtract 1, such as P[current - 1].

• Using the visited array enables fast “read status” checking.

• sys.stdin.read is used to read input quickly.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = list(map(int, data[1:]))
    
    visited = [False] * (N + 1)
    current = 1
    count = 0
    
    while not visited[current]:
        visited[current] = True
        count += 1
        current = P[current - 1]
    
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.