简答题 偏难
#23349

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

信息传递

【问题描述】

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

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

【输入格式】

输入文件名为 message.in。

输入共 2 行。

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

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

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

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

【输出格式】

输出文件名为 message.out。

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

【输入输出样例 1】

【输入输出样例 1 说明】

游戏的流程如图所示。当进行完第 3 轮游戏后,4 号玩家会听到 2 号玩家告诉他自己的生日,所以答案为 3。当然,第 3 轮游戏后,2 号玩家、3 号玩家都能从自己的消息来源得知自己的生日,同样符合游戏结束的条件。

【数据规模与约定】

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

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

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

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include &lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int maxn=200010;</p><p style="text-align: left;">int n, fa[maxn],ans=0x3f3f3f3f;</p><p style="text-align: left;">int get(int x, int &amp;cnt){</p><p style="text-align: left;">    cnt++;</p><p style="text-align: left;">    if(fa[x]==x)return x;</p><p style="text-align: left;">    else return get(fa[x], cnt);</p><p style="text-align: left;">}</p><p style="text-align: left;">int main () {</p><p style="text-align: left;">    cin&gt;&gt;n;</p><p style="text-align: left;">    for(int i=1;i&lt;=n;i++)</p><p style="text-align: left;">        fa[i]=i;</p><p style="text-align: left;">    for(int i=1;i&lt;=n;i++) {</p><p style="text-align: left;">        int cnt=0,f;</p><p style="text-align: left;">        cin&gt;&gt;f;</p><p style="text-align: left;">        if(get(f,cnt)==i){</p><p style="text-align: left;">            ans=min(ans,cnt); </p><p style="text-align: left;">        }else{</p><p style="text-align: left;">        <span style="white-space:pre"> </span>fa[i]=f;</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    cout&lt;&lt;ans;</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。