The Bovine Shuffle

题目描述

农夫约翰坚信快乐的奶牛能产出更多牛奶，于是在牛棚里安装了一个巨大的迪斯科球，并计划教奶牛跳舞！

在查阅流行的奶牛舞蹈后，农夫约翰决定教奶牛一种名为“Bovine Shuffle”的舞蹈。Bovine Shuffle 由他的 $N$ 头奶牛（$1 \leq N \leq 100,000$）以某种顺序排成一行开始，然后连续进行若干次“洗牌”（shuffle），每次洗牌都可能重新排列奶牛。为了便于奶牛找到自己的位置，农夫约翰将队列的位置标记为 $1 \ldots N$：队列中的第一头奶牛在位置 1，第二头在位置 2，依此类推，直到位置 $N$。

一次洗牌用 $N$ 个数字 $a_1 \ldots a_N$ 来描述：处在位置 $i$ 的奶牛在洗牌过程中会移动到位置 $a_i$（因此每个 $a_i$ 都在 $1 \ldots N$ 的范围内）。洗牌时每头奶牛都会移动到它的新位置。

不幸的是，所有的 $a_i$ 不一定互不相同，因此多头奶牛可能会尝试移动到同一个位置；在此之后，它们将合在一起，并在剩余的所有洗牌中一起移动。

农夫约翰注意到，无论进行多少次洗牌，他的队列中有一些位置始终会有奶牛。请帮助他统计这样的位置信息有多少个。

输入格式

第一行输入 $N$，表示奶牛数量。 第二行包含 $N$ 个整数 $a_1 \ldots a_N$。

输出格式

请输出无论进行多少次洗牌都将始终有奶牛存在的位置数量。

4
3 2 1 3

3

提示

输入格式（文件 shuffle.in）： 第一行输入包含 $N$，奶牛数量。下一行包含 $N$ 个整数 $a_1 \ldots a_N$。 输出格式（文件 shuffle.out）： 请输出无论进行多少次洗牌都将始终有奶牛存在的位置数量。 题目来源：Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver