2015年 day2.2 传递信息

传递信息
 
有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学。
  游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?
 
输入格式:
输入共2行。
第1行包含1个正整数n表示n个人。
第2行包含n个用空格隔开的正整数T1,T2,……,Tn其中第i个整数Ti示编号为i
的同学的信息传递对象是编号为Ti的同学,Ti≤n且Ti≠i
数据保证游戏一定会结束。

输出格式:
输出共 1 行,包含 1 个整数,表示游戏一共可以进行多少轮。
 
输入样例:
5
2 4 2 3 1
输出样例:
3
 
//寻找图中的最小环的点的个数,一个人只能向一个传信息,
//所以没有两个环套在一起的情况,数据有点大,做一下预处理,
//将不在环中的点标记再搜索; 
#include<cstdio>
int a[200005],n,sz[200005],ans=200000,m,q;
bool f[200005]={0};
void zhao(int k){
    sz[k]--;
    if(sz[k]==0) {              //到k的入度减一,若入度为零(不在环中),继续标记它能到的点; 
        f[k]=1;
        zhao(a[k]);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){scanf("%d",&a[i]);sz[a[i]]++;}
    for(int i=1;i<=n;i++){
        if(sz[i]==0&&!f[i]){
            f[i]=1;
            zhao(a[i]);        //入度为零,搜索该点,将不在环中的点标记; 
        }
    }
    for(int i=1;i<=n;i++){
        if(!f[i]){             //在环中。。 
            m=1;
            f[i]=1;
            q=i;
            while(!f[a[q]]){   //统计i所在环的点个数;
                m++;           //据测c++递归最深65000多一点,故用循环;
                f[a[q]]=1;
                q=a[q];
            }
            if(m<=ans) ans=m;  //记录最小值; 
        }
    }
    printf("%d
",ans);
    return 0;
}
View Code

 

原文地址:https://www.cnblogs.com/qingang/p/5285660.html