题解：AtCoder AT_awc0030_d Telephone Game of Messages

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderD - 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 ii1 ≤ 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_{k1} T_{a_k}ak1​Tak​​.游戏进行如下首先选择一名起始学生s ss。令a 0 s a_0 sa0​s对于k ≥ 0 k \geq 0k≥0通过a k 1 T a k a_{k1} T_{a_k}ak1​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, \ldotsk1,2,…in order, the following is repeated:初始时a 0 a_0a0​被标记为已访问。然后依次对k 1 , 2 , … k 1, 2, \ldotsk1,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 NNT 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, Ni1,2,…,Nin order, separated by spaces, on a single line.【输入样例】4 2 3 4 2【输出样例】3 3 3 3【算法标签】#图的遍历-DFS#【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;intn,t[N],ans[N];// t: 指向的下一个位置, ans: 存储结果环的长度boolvis[N];// 访问标记// 深度优先搜索计算从节点u开始的环长度voiddfs(intu){// 如果已经计算过直接返回if(ans[u]){return;}// 如果访问到已标记的节点说明找到了环if(vis[u]){intlen1;intvt[u];// 计算环的长度while(v!u){len;vt[v];}// 为环上所有节点设置结果ans[u]len;vt[u];while(v!u){ans[v]len;vt[v];}return;}// 标记当前节点已访问vis[u]true;dfs(t[u]);// 递归探索下一个节点vis[u]false;// 回溯取消标记// 如果当前节点的结果还未计算则继承下一个节点的结果if(!ans[u]){ans[u]ans[t[u]];}}intmain(){cinn;for(inti1;in;i){cint[i];}// 对每个未计算的节点进行DFSfor(inti1;in;i){if(!ans[i]){// 注释掉的调试代码// cout i i endl;// for (int i1; in; i)// cout vis[i] ;// cout endl;dfs(i);}}// 输出结果for(inti1;in;i){coutans[i] ;}coutendl;return0;}【运行结果】4 2 3 4 2 3 3 3 3