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。

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. const int N=200010;
   
4. int n,t[N],r[N],ans=0x7fffff,v[N];
   
5. void dfs(int x,int s,int l)
   
6. {
   
7.     if(x==s&&l)
   
8.     {
   
9.         ans=min(ans,l);
   
10.         return;
    
11.     }
    
12.     if(!v[t[x]])
    
13.     {
    
14.         v[t[x]]=1;
    
15.         dfs(t[x],s,l+1);
    
16.     }
    
17. }
    
18. void del(int x)
    
19. {
    
20.     v[x]=-1;
    
21.     r[t[x]]--;
    
22.      if(!r[t[x]]&&v[t[x]]!=-1)del(t[x]);
    
23. }
    
24. int main()
    
25. {
    
26.     cin>>n;
    
27.     for(int i=1;i<=n;i++)
    
28.     {
    
29.         cin>>t[i];
    
30.         r[t[i]]++;
    
31.     }
    
32.     for(int i=1;i<=n;i++)
    
33.         if(!r[i]&&v[i]!=-1)del(i);
    
34.     for(int i=1;i<=n;i++)
    
35.         if(!v[i])dfs(i,i,0);
    
36.     cout<<ans<<endl;
    
37. }
    

复制代码

秀木于林

1. #include<iostream>
   
2. using namespace std;
   
3. const int mm=201000;
   
4. int n,t[mm],b=0,p=0,a[mm],ans=99999999;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     for(int i=1; i<=n; i++) cin>>t[i];
   
9.     ///----1----///
   
10.     for(int i=1,j; i<=n; i++)
    
11.     {
    
12.         if(!a[i])
    
13.         {
    
14.             int now=++p;
    
15.             for(j=i; !a[j]; j=t[j])
    
16.                 a[j]=++p;
    
17.             if(a[j]>now) ans=min(ans,p-a[j]+1);
    
18.         }
    
19.     }
    
20.     cout<<ans;
    
21.     return 0;
    
22. }
    
23. 
    

复制代码