Codevs 4511 信息传递

article/2025/7/6 5:22:10

题目描述 Description

有个同学（编号为 1 到）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为的同学的信息传递对象是编号为的同学。游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

输入描述 Input Description

输入共 2行。

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

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

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

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

输出描述 Output Description

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

信息传递这道题，也属于一个很久很久没能A的题，这段时间也成功A了。

基本思路是，对连续的一些点进行编号，如果当要编号时，这个该被编号的点已经有编号了，那么这个点一定是一个自环的开头了。因为可以看做从环首开始，再到环首结束的一次游戏，所以这时答案就是该编的号-本来的编号。接着再从没有编号的点开始枚举。

不过这个题有一个特殊情况，如下图。

当把数字1所连的环判完之后，再从二的右下角开始，也会发现当该编号时，该编号的点已经被编号，所以需要记录每一个点所在的层数，如红色为1，黑色为2，如果层数不相等，那么直接return掉这种情况，因为答案还是会与之前一样，是这个环的长度。

#include<iostream>
#include<queue>
#define maxn 200005
using namespace std; 
int n;
int mes[maxn];
int vis[maxn];
int cnt,ans=999999999;
bool flag=true;
int dep[maxn];
void dfs(int now,int d)
{if(flag==false) return;cnt++;if(vis[now] && dep[now]!=d){flag=false;return;}if(vis[now]){ans=min(ans,cnt-vis[now]);flag=false;return;}vis[now]=cnt;dep[now]=d;dfs(mes[now],d);
}
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>mes[i];for(int i=1;i<=n;i++)if(vis[i]==0){cnt=0;flag=true;dfs(i,i);	}cout<<ans<<endl;
}