ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 F: PolandBall and Forest

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：32 通过：18
返回比赛提交提交记录

题目描述

波兰鲍尔和他的家人住在森林里。森林里有一些树。树是具有 k 顶点和 k-1 条边的无向无环图，其中 k 是某个整数。请注意，一个顶点是有效的树。
每棵树的每个顶点中只有一个亲戚，它们具有从 1 到 n 的唯一 ID。对于每个球，我们知道它住在同一棵树上的最远亲的ID。如果有几个这样的顶点，我们只知道其中 id 最小的顶点的值。
森林里有多少棵树？
PolandBall lives in a forest with his family. There are some trees in the forest. Trees are undirected acyclic graphs with k vertices and k-1 edges, where k is some integer. Note that one vertex is a valid tree.
There is exactly one relative living in each vertex of each tree, they have unique ids from 1 to n. For each Ball i we know the id of its most distant relative living on the same tree. If there are several such vertices, we only know the value of the one with smallest id among those.
How many trees are there in the forest?
Input
The first line contains single integer n (1≤n≤104)− the number of Balls living in the forest.
The second line contains a sequence p1,p2,...,pn of length n, where (1≤pi≤n) holds and pi denotes the most distant from Ball i relative living on the same tree. If there are several most distant relatives living on the same tree, pi is the id of one with the smallest id.
It's guaranteed that the sequence p corresponds to some valid forest.
Hacking: To hack someone, you should provide a correct forest as a test. The sequence p will be calculated according to the forest and given to the solution you try to hack as input. Use the following format:
In the first line, output the integer n (1≤n≤104)− the number of Balls and the integer m (0≤m<n)− the total number of edges in the forest. Then m lines should follow. The i-th of them should contain two integers ai and bi and represent an edge between vertices in which relatives ai and bi live. For example, the first sample is written as follows:
5 3
1 2
3 4
4 5
Output
You should output the number of trees in the forest where PolandBall lives.
Interaction
From the technical side, this problem is interactive. However, it should not affect you (except hacking) since there is no interaction.
Examples
Input 
5
2 1 5 3 3
Output 
2
Input
1
1
Output 
1
Note
In the first sample testcase, possible forest is: 1-2 3-4-5.
There are 2 trees overall.
In the second sample testcase, the only possible graph is one vertex and no edges. Therefore, there is only one tree.

输入格式

输入
第一行包含单个整数 n (1≤N≤104）− 生活在森林中的球的数量。
 第二行包含一个序列p1，p2,...,pn长度为 n，其中 （1≤p我≤n） 保留和p我表示与Ball i最远的亲戚住在同一棵树上。如果有几个最远的亲戚住在同一棵树上，p我是具有最小 id 的 id。保证序列 p 对应于某个有效的森林。
黑客：要入侵某人，您应该提供正确的森林作为测试。序列 p 将根据森林计算，并作为输入提供给您尝试破解的解决方案。使用以下格式：
在第一行中，输出整数 n (1≤N≤104）− 球的数量和整数 m （0≤m<n）− 森林中边的总数。然后 m 行应该紧随其后。其中的第 i 个应包含两个整数一个我和b我并表示顶点之间的边，其中亲戚一个我和b我住。例如，第一个示例编写如下：

输出格式

输出
您应该输出 PolandBall 居住的森林中的树木数量。
Input 
5
2 1 5 3 3
Output 
2
Input
1
1
Output 
1


输入样例 复制 

5
2 1 5 3 3

输出样例 复制 

2

分类标签