luogu P3420 [POI2005]SKA-Piggy Banks
题目描述
Byteazar the Dragon has NN 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.
有n个储钱罐,每个的钥匙都在另一个里面,求取出所有储钱罐中的钱最少要砸开几个
输入输出格式
输入格式:
The first line of the standard input contains a single integer NN (1\le N\le 1\ 000\ 0001≤N≤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 11 to NN. Next, there are NNlines: the (i+1)(i+1)'st line contains a single integer - the number of the piggy bank in which the ii'th key has been placed.
输出格式:
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.
输入输出样例
4
2
1
2
4
2 并查集,由于每个盒子的入度只能是1,既然能并到一起,那么一定有一个起始节点;
最后统计集合个数
#include<cstdio>
int n;
const int maxn = ;
int a[maxn];
int father[maxn];
int find(int x) {
if(father[x]!=x)father[x]=find(father[x]);
return father[x];
}
void unionn(int x,int y) {
int fx=find(x),fy=find(y);
if(fx!=fy)father[fx]=fy;
}
int main () {
scanf("%d",&n);
for(int i=;i<=n;++i)father[i]=i;
for(int i=;i<=n;++i) {
scanf("%d",a+i);unionn(i,a[i]);
}
int ans=;
for(int i=;i<=n;++i)
if(father[i]==i)ans++;
printf("%d\n",ans);
return ;
}
最新文章
- Failed to stop iptables.service: Unit iptables.service not loaded.
- STL的std::find和std::find_if
- 【Alpha】Daily Scrum Meeting第一次
- javascript高级编程3第三章:基本概念 本章内容 语法 数据类型 流控制语句 函数
- 【bzoj4034】[HAOI2015]树上操作
- 【20140113-2】MyEclipse生成javadoc时出错:编码GBK的不可映射字符
- mathematica练习程序(图像取反)
- 安装xubuntu时遇到的一些问题
- 使用OutputDebugString输出调试信息
- 桂电在线-php-提取菜单到配置文件2
- 【HDOJ】1510 White Rectangles
- Apache Tomcat8必备知识
- OCP-1Z0-051-题目解析-第9题
- yii框架中关于控制器中filter过滤器和外部action的使用
- Java IO 学习总结 学习手册总结
- Android热修复(动态加载)方案汇总
- Shiro【授权、整合Spirng、Shiro过滤器】
- 10 Free Image Hosting Sites for Your Photos
- loopback 代码解析
- [原] jQuery EasyUI 1.3.4 离线API、Demo (最新)