#P3037. 创世纪

    ID: 2169 传统题 1000ms 512MiB 尝试: 639 已通过: 215 难度: 6 上传者: 标签>CF2100提高功能图入度剥离树形 DP线性 DP断环成链补集转化Poetize4

创世纪

题目描述

applepi 手里有一本书《创世纪》,里面记录了这样一个故事……

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

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

输入格式

第一行是一个整数 n n ,表示世界元素的数目。

第二行有 n n 个整数 a1,a2,…,an a_1, a_2, …, a_n 。ai a_i 表示第 i i 个世界元素能够限制的世界元素的编号。

输出格式

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

样例输入

6
2 3 1 3 6 5

样例输出

3

提示

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

数据规模与约定

对于 30%30\% 的数据,n≤10 n\leq 10 。

对于 60%60\% 的数据,n≤1×105 n\leq 1\times 10^5 。

对于 100%100\% 的数据,n≤1×106 n\leq 1\times 10^6 ,1≤ai≤n 1\leq a_i\leq n ,ai≠i a_i\neq i 。

题目来源

Poetize4