- 题目提供者 洛谷
- 评测方式 云端评测
- 标签 并查集 概率论,统计 连通块 POI 2005 高性能
- 难度 普及+/提高
- 时空限制 1000ms / 128MB
Byteazar the Dragon has $N$ piggy banks. Each piggy bank can either be opened with its corresponding key or smashed. Byteazar has put the keys in some of the piggy banks - he remembers which key has been placed in which piggy bank. Byteazar intends to buy a car and needs to gain access to all of the piggy banks. However, he wants to destroy as few of them as possible. Help Byteazar to determine how many piggy banks have to be smashed.
TaskWrite a programme which:
reads from the standard input the number of piggy banks and the deployment of their corresponding keys,finds the minimal number of piggy banks to be smashed in order to gain access to all of them,writes the outcome to the standard output.
Byteazar the Dragon拥有N个小猪存钱罐。每一个存钱罐能够用相应的钥匙打开或者被砸开。Byteazar已经将钥匙放入到一些存钱罐中。现在已知每个钥匙所在的存钱罐，Byteazar想要买一辆小汽车，而且需要打开所有的存钱罐。然而，他想要破坏尽量少的存钱罐，帮助Byteazar去决策最少要破坏多少存钱罐。
The first line of the standard input contains a single integer $N$ ($1\le N\le 1\ 000\ 000$) - this is the number of piggy banks owned by the dragon. The piggy banks (as well as their corresponding keys) are numbered from $1$ to $N$. Next, there are $N$ lines: the $(i+1)$'st line contains a single integer - the number of the piggy bank in which the $i$'th key has been placed.
第一行：包括一个整数N（1<=N<=1000000)，这是Byteazar the Dragon拥有的存钱罐的数量。
The first and only line of the standard output should contain a single integer - the minimal number of piggy banks to be smashed in order to gain access to all of the piggy banks.