| 题目名称 | 2105. [NOIP 2015]信息传递 |
|---|---|
| 输入输出 | 2015message.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Satoshi
于2015-11-17加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：467， 提交：1657， 通过率：28.18% | ||||
 ShallowDream雨梨 |
100 | 0.040 s | 6.60 MiB | C++ |
 cy |
100 | 0.046 s | 0.26 MiB | C++ |
|
ShallowDream雨梨 |
100 | 0.047 s | 6.38 MiB | C++ |
|
ShallowDream雨梨 |
100 | 0.047 s | 6.38 MiB | C++ |
 dateri |
100 | 0.049 s | 1.36 MiB | C++ |
 Hyoi_0Koto |
100 | 0.050 s | 1.42 MiB | C++ |
 HtBest |
100 | 0.050 s | 15.55 MiB | C++ |
|
cy |
100 | 0.052 s | 1.36 MiB | C++ |
 KCkwok |
100 | 0.053 s | 9.28 MiB | C++ |
|
Hyoi_0Koto |
100 | 0.055 s | 1.42 MiB | C++ |
| 本题关联比赛 | |||
| 图的简单问题 | |||
| 图的简单问题 | |||
| 关于 信息传递 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
呵呵呵
| ||||
|
第一道topo判环留念~
第一次手写快读留念~ 1A留念~ | ||||
|
| ||||
|
回复 @snake :
| ||||
|
| ||||
|
| ||||
|
在洛谷过了在这wa了什么鬼.......
----------------------------------- 洛谷数据真水 | ||||
|
拓扑删不成环的点，dfs找环，好像进rank的很少这么做
| ||||
|
回复 @hzoi_WildRage :
 猛牛盐酸乳
2017-06-09 19:43
27楼
| ||||
ignitedark
leon
+1s
JustWB【题目描述】
有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。
【来源】
在此键入。