#4930. [USACO13FEB] Message Relay G

[USACO13FEB] Message Relay G

题目描述

农夫约翰有N头奶牛(1 ≤ N ≤ 1000),编号从1到N。这些奶牛使用一种基于锡罐和绳子的古老通信机制,能够在约翰不知情的情况下相互传递信息。

每头奶牛最多只能将信息转发给另一头奶牛:对于奶牛i,F(i)表示她会将收到的信息转发给哪头奶牛(这个数字总是不同于i本身)。如果F(i)为0,则表示奶牛i不会转发信息。

不幸的是,奶牛们发现某些奶牛发出的信息可能会陷入无限循环。如果从某头奶牛发出的信息最终会陷入循环转发,则称这头奶牛是"循环的"。奶牛们希望避免从循环的奶牛发送信息。请你帮助她们统计农夫约翰的牛群中非循环奶牛的总数。

输入格式

第一行包含一个整数N,表示奶牛的数量。

接下来的N行,第i+1行包含F(i)的值,表示奶牛i的转发对象。

输出格式

输出一个整数,表示非循环奶牛的数量。

输入输出样例

输入 #1

5
0
4
1
5
4

输出 #1

2

样例解释

输入中有5头奶牛:

  • 奶牛1不转发信息(F(1)=0)
  • 奶牛2转发给奶牛4(F(2)=4)
  • 奶牛3转发给奶牛1(F(3)=1)
  • 奶牛4转发给奶牛5(F(4)=5)
  • 奶牛5转发给奶牛4(F(5)=4)

非循环奶牛有:

  • 奶牛1(不转发信息)
  • 奶牛3(转发给奶牛1后停止)

其他奶牛都会形成转发循环(2→4→5→4...),因此输出结果为2。