← 返回题目列表

AtCoder · awc0093_b

B. 消息转发

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥正在与一组人进行消息转发实验 N 成员。

成员编号为 1 to N,以及每个成员 i (1 \leq i \leq N) 恰好有一个预定的转发目的地会员号码 P_i (其中 P_i \neq i).

高桥给会员留言 1。该消息始终由一个成员持有,并且最初是一个成员 1 持有它。收到该消息的成员被记录为 已收到。会员 1 被认为在开始时已收到消息,因此被标记为已收到。

之后按照以下规则重复转发:

  1. 让 i 是当前持有该消息的成员。
  2. 检查是否是会员 P_i,会员转发目的地 i,已收到消息。
  • 如果会员 P_i 有 尚未收到 会员留言 i 将消息转发给会员 P_i。结果,会员 i 不再保留该消息,并且会员 P_i 现在保存该消息。会员 P_i 按接收状态记录。然后,返回步骤 1。
  • 如果会员 P_i 有 已收到 消息,不进行转发,实验结束会员 i 仍然保留着这条消息。

确定实验结束时已记录为接收的成员数量(包括成员) 1).

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq N
  • P_i \neq i (1 \leq i \leq N)
  • 所有输入均为整数

输入

N
P_1 P_2 \ldots P_N
  • 第一行包含一个整数 N,代表会员数量。
  • 第二行包含整数 P_1, P_2, \ldots, P_N,代表会员的转发目的地号码 1, 2, \ldots, N 分别按此顺序用空格分隔。

输出

在一行中打印实验结束时已记录的成员数量。


示例输入 1

4
2 3 4 1

示例输出 1

4

示例输入 2

6
3 1 2 5 6 4

示例输出 2

3

示例输入 3

10
2 3 1 5 6 7 8 9 10 4

示例输出 3

3