题解：AtCoder AT_awc0030_d Telephone Game of Messages

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：D - Telephone Game of Messages

【题目描述】

There areN NNstudents in Takahashi’s class, numbered from1 11toN NN. The class plays a message-passing game (telephone game).
高桥的班上有N NN名学生，编号从1 11到N NN。这个班级在玩一个传话游戏（电话游戏）。

For each studenti ii(1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N), there is exactly one designated studentT i T_iTi​to whom they pass the message (T i ≠ i T_i \neq iTi​=i).
对于每名学生i ii（1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N），恰好有一名指定的学生T i T_iTi​作为其传话对象（T i ≠ i T_i \neq iTi​=i）。

The game proceeds as follows. First, a starting students ssis chosen. Leta 0 = s a_0 = sa0​=s, and fork ≥ 0 k \geq 0k≥0, define the sequencea 0 , a 1 , a 2 , … a_0, a_1, a_2, \ldotsa0​,a1​,a2​,…bya k + 1 = T a k a_{k+1} = T_{a_k}ak+1​=Tak​​.
游戏进行如下：首先，选择一名起始学生s ss。令a 0 = s a_0 = sa0​=s，对于k ≥ 0 k \geq 0k≥0，通过a k + 1 = T a k a_{k+1} = T_{a_k}ak+1​=Tak​​定义序列a 0 , a 1 , a 2 , … a_0, a_1, a_2, \ldotsa0​,a1​,a2​,…。

Initially,a 0 a_0a0​is marked as “visited.” Then, fork = 1 , 2 , … k = 1, 2, \ldotsk=1,2,…in order, the following is repeated:
初始时，a 0 a_0a0​被标记为"已访问"。然后，依次对k = 1 , 2 , … k = 1, 2, \ldotsk=1,2,…重复以下操作：

• Ifa k a_kak​is already visited, the message stops there.
  如果a k a_kak​已被访问，则消息在此处停止。
• Otherwise, marka k a_kak​as visited and proceed to the nextk kk.
  否则，将a k a_kak​标记为已访问，并继续下一个k kk。

Since the number of students is finite, the message always stops after a finite number of steps.
由于学生人数有限，消息总是会在有限步后停止。

Letv vvdenote the student reached when the process stops (i.e.,a k a_kak​at the time of stopping). The studentv vvwas previously marked as visited, and repeatedly applyingT TTstarting fromv vvwill eventually return tov vv. That is, following the pathv , T v , T T v , … v, T_v, T_{T_v}, \ldotsv,Tv​,TTv​​,…will eventually reachv vvagain. The number of students on the path starting fromv vvand returning tov vv(includingv vvitself) is called themessage loop lengthfor starting students ss.
设v vv表示过程停止时到达的学生（即停止时的a k a_kak​）。学生v vv先前已被标记为已访问，从v vv开始重复应用T TT最终会回到v vv。也就是说，沿着路径v , T v , T T v , … v, T_v, T_{T_v}, \ldotsv,Tv​,TTv​​,…最终会再次到达v vv。从v vv出发并回到v vv的路径上的学生人数（包括v vv自身）称为起始学生s ss的消息环长度。

For each case where the message starts from student1 11, student2 22, …, studentN NN, find the message loop length.
对于消息分别从学生1 11、学生2 22、……、学生N NN开始的情况，求消息环长度。

【输入】

N NN
T 1 T_1T1​T 2 T_2T2​… \ldots…T N T_NTN​

• The first line contains an integerN NN, representing the number of students.
• The second line containsN NNintegersT i T_iTi​, separated by spaces, representing the recipient of each studenti ii’s message.

【输出】

C 1 C_1C1​C 2 C_2C2​… \ldots…C N C_NCN​

• LetC i C_iCi​be the message loop length when the message starts from studenti ii. OutputC i C_iCi​fori = 1 , 2 , … , N i = 1, 2, \ldots, Ni=1,2,…,Nin order, separated by spaces, on a single line.

【输入样例】

4 2 3 4 2

【输出样例】

3 3 3 3

【算法标签】

#图的遍历-DFS#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;intn,t[N],ans[N];// t: 指向的下一个位置, ans: 存储结果（环的长度）boolvis[N];// 访问标记// 深度优先搜索，计算从节点u开始的环长度voiddfs(intu){// 如果已经计算过，直接返回if(ans[u]){return;}// 如果访问到已标记的节点，说明找到了环if(vis[u]){intlen=1;intv=t[u];// 计算环的长度while(v!=u){len++;v=t[v];}// 为环上所有节点设置结果ans[u]=len;v=t[u];while(v!=u){ans[v]=len;v=t[v];}return;}// 标记当前节点已访问vis[u]=true;dfs(t[u]);// 递归探索下一个节点vis[u]=false;// 回溯，取消标记// 如果当前节点的结果还未计算，则继承下一个节点的结果if(!ans[u]){ans[u]=ans[t[u]];}}intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>t[i];}// 对每个未计算的节点进行DFSfor(inti=1;i<=n;i++){if(!ans[i]){// 注释掉的调试代码// cout << "i " << i << endl;// for (int i=1; i<=n; i++)// cout << vis[i] << " ";// cout << endl;dfs(i);}}// 输出结果for(inti=1;i<=n;i++){cout<<ans[i]<<" ";}cout<<endl;return0;}

【运行结果】

4 2 3 4 2 3 3 3 3