华师一附中OI组

标题: P2661 信息传递 [打印本页]

作者: 倚窗倾听风吹雨 时间: 2018-9-19 19:39
标题: P2661 信息传递
https://www.luogu.org/problemnew/show/P2661

题目描述
有 n 个同学（编号为 1 到 n ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 T_i的同学。

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

输入输出格式
输入格式：
共2行。

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

第2行包含 n 个用空格隔开的正整数 T 1,T 2，其中第 i 个整数T_i表示编号为i 的同学的信息传递对象是编号为T i的同学，Ti≤n 且Ti≠i 。

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

输入输出样例
输入样例#1：
5
2 4 2 3 1
输出样例#1：
3
说明
样例1解释

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

对于 30%的数据， n≤200；

对于 60%的数据， n≤2500；

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

作者: 倚窗倾听风吹雨 时间: 2018-9-19 19:45

#include<iostream>
using namespace std;
const int N=200010;
int n,t[N],r[N],ans=0x7fffff,v[N];
void dfs(int x,int s,int l)
{
if(x==s&&l)
{
ans=min(ans,l);
return;
}
if(!v[t[x]])
{
v[t[x]]=1;
dfs(t[x],s,l+1);
}
}
void del(int x)
{
v[x]=-1;
r[t[x]]--;
if(!r[t[x]]&&v[t[x]]!=-1)del(t[x]);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>t[i];
r[t[i]]++;
}
for(int i=1;i<=n;i++)
if(!r[i]&&v[i]!=-1)del(i);
for(int i=1;i<=n;i++)
if(!v[i])dfs(i,i,0);
cout<<ans<<endl;
}

复制代码

作者: 秀木于林 时间: 2020-1-11 10:44

#include<iostream>
using namespace std;
const int mm=201000;
int n,t[mm],b=0,p=0,a[mm],ans=99999999;
int main()
{
cin>>n;
for(int i=1; i<=n; i++) cin>>t[i];
///----1----///
for(int i=1,j; i<=n; i++)
{
if(!a[i])
{
int now=++p;
for(j=i; !a[j]; j=t[j])
a[j]=++p;
if(a[j]>now) ans=min(ans,p-a[j]+1);
}
}
cout<<ans;
return 0;
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)