6401 创世纪 0x60「图论」例题
描述
上帝手中有 N(N≤10^6) 种世界元素,每种元素可以限制另外1种元素,把第 i 种世界元素能够限制的那种世界元素记为 A[i]。现在,上帝要把它们中的一部分投放到一个新的空间中去建造世界。为了世界的和平与安宁,上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素限制它。上帝希望知道,在此前提下,他最多可以投放多少种世界元素?
输入格式
第一行是一个整数N,表示世界元素的数目。
第二行有N 个整数A1, A2, …, AN。Ai 表示第i 个世界元素能够限制的世界元素的编号。
输出格式
一个整数,表示最多可以投放的世界元素的数目。
样例输入
6 2 3 1 3 6 5
样例输出
3
数据范围与约定
- 对于30%的数据:
- 对于60%的数据:
- 对于100%的数据:
样例解释
对于30% 的数据,N≤10。
对于100% 的数据,N≤10^6,1≤Ai≤N。
来源
石家庄二中【Nescafé 8】杯NOIP模拟赛