免费咨询期/网站如何做seo推广

   日期:2024-12-24     作者:xu1a5       评论:0    移动:http://oml01z.riyuangf.com/mobile/news/7703.html
核心提示:问题描述 n 个小朋友正在做一个游戏,每个人要分享一个自己的小秘密。 每个小朋友都有一个 1 到 n 的编号,编号不重

问题描述
n 个小朋友正在做一个游戏,每个人要分享一个自己的小秘密。
每个小朋友都有一个 1 到 n 的编号,编号不重复。
为了让这个游戏更有趣,老师给每个小朋友发了一张卡片,上面有一个 1 到 n 的数字,每个数字正好出现一次。
每个小朋友都将自己的秘密写在纸上,然后根据老师发的卡片上的数字将秘密传递给对应编号的小朋友。如果老师发给自己的数字正好是自己的编号,这个秘密就留在自己手里。
小朋友们拿到其他人的秘密后会记下这个秘密,老师会再指挥所有小朋友将手中的秘密继续传递,仍然根据老师发的卡片上的数字将秘密传递给对应编号的小朋友。
这样不断重复 n 次。
现在,每个小朋友都记下了很多个秘密。
老师现在想找一些小朋友,能说出所有秘密,请问老师最少要找几个小朋友
输入格式
​ 输入的第一行包含一个整数 n。
第二行包含 n 个整数 a[1], a[2], …, a[n],相邻的整数间用空格分隔,分别表示编号 1 到 n 的小朋友收到的数字。
输出格式
输出一行包含一个整数,表示答案。
样例输入
6
2 1 3 5 6 4
样例输出
3
样例说明
最终小朋友 1, 2 互相知道了对方的秘密,小朋友 3 只知道自己的秘密,小朋友 4, 5, 6 互相知道了对方的秘密。
至少要找 3 个小朋友才能说出所有秘密。
评测用例规模与约定
对于 30% 的评测用例,2 <= n <= 30。
对于 60% 的评测用例,2 <= n <= 1000。
对于所有评测用例,2 <= n <= 100000。

免费咨询期/网站如何做seo推广


题解该题是一道并查集的问题。我们只需要将相同关系的合并起来(shu[x]!=x的时候合并关系,最后看一共有多少个关系就可以了。(就是将相互之间交换可以得到的合成一个。

拿例题来说,最初的序列为:2 1 3 5 6 4;经操作之后可以的到shu数组为:2,2,3,4,4,4数字相同的属于同一关系,我们最后查看有多少不同的数字就可。

代码如下: 

 
特别提示:本信息由相关用户自行提供,真实性未证实,仅供参考。请谨慎采用,风险自负。

举报收藏 0打赏 0评论 0
 
更多>同类最新资讯
0相关评论

相关文章
最新文章
推荐文章
推荐图文
最新资讯
点击排行
{
网站首页  |  关于我们  |  联系方式  |  使用协议  |  隐私政策  |  版权隐私  |  网站地图  |  排名推广  |  广告服务  |  积分换礼  |  网站留言  |  RSS订阅  |  违规举报  |  鄂ICP备2020018471号