5561.创世纪

时间限制:1s 内存限制:256MB

上帝手中有着 $N$ 种被称作“世界元素”的东西,现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素,所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它,这样上帝就可以保持对世界的控制。

由于那个著名的有关于上帝能不能制造一块连自己都不能举起的大石头的二律背反命题,我们知道上帝不是万能的,而且不但不是万能的,他甚至有事情需要找你帮忙——上帝希望知道他最多可以投放多少种世界元素,但是他只会 $O(2^N )$ 级别的算法。虽然上帝拥有无限多的时间,但是他也是个急性子。

你需要帮助上帝解决这个问题。

输入格式(从终端/标准输入读取)

第一行是一个整数 $N$,表示世界元素的数目。
第二行有 $N$ 个整数 $A_1 , A_2 , ..., A_N$ 。$A_i$ 表示第 $i$ 个世界元素能够限制的世界元素的编号。

输出格式(输出至终端/标准输出)

一个整数,表示最多可以投放的世界元素的数目。

输入样例

复制
6
2 3 1 3 6 5
 \n
 · · · · · \n

输出样例

复制
3
 \n

说明

样例说明

选择 $2、3、5$ 三个世界元素即可。分别有 $1、4、6$ 来限制它们。

数据范围与约定

对于 30% 的数据,$N≤10$。
对于 100% 的数据,$N≤10^6 ,1≤A_i ≤N,A_i ≠i$。

来源: 进阶指南 图论 基环树

提交题解

Please login first.

© 2025 FAQs