#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。