题目名称 2105. [NOIP2015] 信息传递
输入输出 2015message.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2015-11-17
开放分组 全部用户
提交状态
分类标签
搜索法 图论 NOIP 连通性
通过:271, 提交:1538, 通过率:17.62%
GravatarHeHe 100 0.044 s C++
GravatarKCkwok 100 0.045 s C++
Gravatarcy 100 0.046 s C++
Gravatardateri 100 0.049 s C++
GravatarHyoi_0Koto 100 0.050 s C++
GravatarHtBest 100 0.050 s C++
Gravatarcy 100 0.052 s C++
GravatarHyoi_0Koto 100 0.055 s C++
GravatarAntiLeaf 100 0.060 s C++
GravatarLB 100 0.065 s C++
关于 信息传递 的讨论
有向图的最小环问题,可用深搜遍历解决。
Gravatarnsnsjsjjs
2015-11-09 20:28 1楼
回复 @nsnsjsjjs :
我给满分!
Gravatar柯哀王道
2015-11-09 21:42 2楼
回复 @nsnsjsjjs :
我给你6个6!
Gravataregc
2015-11-11 20:49 3楼
回复 @nsnsjsjjs :
这逼装的有点生硬!满分!
Gravatar铁桶僵尸
2015-11-09 21:44 4楼
回复 @nsnsjsjjs :
666666--标准的六个六
Gravatar铁桶僵尸
2015-11-09 21:45 5楼
唯一一个上榜的Pascal飘过……
GravatarMarvolo
2015-11-10 13:36 6楼
我的代码仅30行,但无奈最后的一个数据超时。。。。
GravatarO(1)
2015-11-12 17:10 7楼
为毛无优化开关E一个点,O2优化全过,NOIP不会全E掉吧!!!
Gravatarzys
2015-11-15 07:26 8楼
回复 @0_0 :
因为最后一个测试点是一个环~~~~会爆栈~~~
GravatarOI永别
2015-11-19 15:24 9楼
考场上没有想到一楼的好主意,DAY1太慌焦虑
GravatarNVIDIA
2015-11-21 16:03 10楼
为什么我在windows下测爆栈。。。。。。
GravatarTCtower
2015-11-22 21:25 11楼
额,还好我是普及组
Gravatarsnake
2015-12-05 16:16 12楼
Gravatar+1s
2018-02-06 10:02 13楼
回复 @MC万岁 :
Hello Changhao
Gravatarsnake
2015-12-05 16:45 14楼
回复 @snake :
Gravatar+1s
2018-02-06 10:02 15楼
W六次,过了........
GravatarYGOI_真神名曰驴蛋蛋
2016-01-14 10:26 16楼
练练tarjan
Gravatarliu_runda
2016-01-22 09:44 17楼
被刷下去辣 dalao们太强辣
GravatarJanis
2016-10-09 20:15 18楼
一定要在size>1时比较答案
Gravatar_Itachi
2016-08-28 08:41 19楼
递归无压力
手工栈的悲哀
GravatarAntiLeaf
2016-08-28 21:35 20楼
GravatarLOSER
2016-10-09 07:37 21楼
被逼无奈, 开大栈了.
Gravatar小e
2016-10-26 21:18 22楼
乱搞ac
GravatarRapiz
2016-11-04 11:04 23楼
感觉自己好像啥算法都没用。。。
瞎猫碰到死耗子。。。
GravatarZwoi_只会打表抄代码的蒟蒻
2016-11-06 18:11 24楼
环啊~环啊~~~~
GravatarAys
2016-11-16 18:52 25楼
Gravatar+1s
2018-02-06 10:02 26楼
GravatarHzoi_Hugh
2017-03-17 13:58 27楼
GravatarWildRage
2017-03-25 10:08 28楼
回复 @hzoi_WildRage :
Gravatar猛牛盐酸乳
2017-06-09 19:43 29楼
回复 @hzoi_WildRage :
666666[/size][/size][/size][/size][/size][/size][/size][/size][/size][/size]
Gravatar猛牛盐酸乳
2017-06-09 19:42 30楼
回复 @nsnsjsjjs :
我给你个6
剩下的4给超时
剩下的90给没ac
Gravatar+1s
2017-09-16 13:17 31楼
拓扑删不成环的点,dfs找环,好像进rank的很少这么做
GravatarHyoi_0Koto
2017-09-16 16:14 32楼
在洛谷过了在这wa了什么鬼.......
-----------------------------------
洛谷数据真水
GravatarJustWB
2017-11-08 16:23 33楼

2105. [NOIP2015] 信息传递

★☆   输入文件:2015message.in   输出文件:2015message.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学。

游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?

【输入格式】

输入共2行。

第1行包含1个正整数n表示n个人。

第2行包含n个用空格隔开的正整数T1,T2,……,Tn其中第i个整数Ti示编号为i

的同学的信息传递对象是编号为Ti的同学,Ti≤n且Ti≠i

数据保证游戏一定会结束。

【输出格式】

输出共 1 行,包含 1 个整数,表示游戏一共可以进行多少轮。

【样例输入】


5

2 4 2 3 1


【样例输出】

 3

【提示】



游戏的流程如图所示。当进行完第 3 轮游戏后, 4 号玩家会听到 2 号玩家告诉他自

己的生日,所以答案为 3。当然,第 3 轮游戏后, 2 号玩家、 3 号玩家都能从自己的消息

来源得知自己的生日,同样符合游戏结束的条件。


对于 30%的数据, n ≤ 200;

对于 60%的数据, n ≤ 2500;

对于 100%的数据, n ≤ 200000。


【来源】

在此键入。