首页 > 代码库 > [NOIP2015]信息传递
[NOIP2015]信息传递
[NOIP2015]信息传递
【问题描述】
有??个同学（编号为1到??）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为?? 的同学的信息传递对象是编号为????的同学。游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？
【输入格式】
输入文件名为message.in。
输入共2行。
第1行包含1个正整数??，表示??个人。
第2行包含?? 个用空格隔开的正整数??1,??2,……,????，其中第?? 个整数????表示编号为??的同学的信息传递对象是编号为Ti的同学，????≤?? 且????≠??。
数据保证游戏一定会结束。
【输出格式】
输出文件名为message.out。
输出共1行，包含1个整数，表示游戏一共可以进行多少轮。
【输入输出样例】
message.in
5
2 4 2 3 1
message.out
3
游戏的流程如图所示。当进行完第3轮游戏后，4号玩家会听到2号玩家告诉他自己的生日，所以答案为3。当然，第3轮游戏后，2号玩家、3号玩家都能从自己的消息来源得知自己的生日，同样符合游戏结束的条件。
【数据规模与约定】
对于30%的数据，??≤200；
对于60%的数据，??≤2500；
对于100%的数据，??≤200000。
这天洛谷莫名其妙地登不上去了，在vijos上边交的AC了。
这个东西可以给他变成一个有向图，其中每一个。。。节点的出度为1，每一个节点的入度的和是n。。。
比如说下图中的这个(请暂时忽略掉有颜色的东西；)
然后是思路：
很容易想到我们要找到最小环的长度，因为在最小环上传递的信息能够最先看到(自己想一想就能明白了)。
为了求最小环方便，我们首先就是去掉入度为0的点，因为这些点不会接受到任何消息(也不会在环中出现)，怎么去掉呢？用一个数组记录它的入度就行了。
与此同时，如果我们去掉了一个入度为0的点导致另一个点的入度变为0，那么把另一个点也去掉，依次类推。
这样子就剩下了一个只剩环的图了。我们用一个d数组来记录就行了。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,to[200001],fromcnt[200001]={0},d[200001],ans=999999;
bool dev[200001];
void ts()//调试
{
printf("************\n");
printf("%d\n",n);
for(int i=1;i<=n;i++)
printf("%5d",to[i]);
printf("\n");
for(int i=1;i<=n;i++)
printf("%5d",fromcnt[i]);
printf("\n");
for(int i=1;i<=n;i++)
printf("%5d",d[i]);
printf("\n");
for(int i=1;i<=n;i++)
printf("%5d",dev[i]);
printf("\n");
printf("************\n");
}
void NaOH(int x)//利用NaOH的强腐蚀性腐蚀掉不在环中的点
{
dev[x]=true;//dev[x]就表示x节点是否被删除
fromcnt[to[x]]--;//让x指向的节点的入度-1
if(fromcnt[to[x]]==0)//如果入度为0
NaOH(to[x]);//利用NaOH的强腐蚀性把指向的那个点腐蚀掉
}
int dfs(int x,int src,int deep)//深度优先搜索
{
if(dev[x])return 0;
// printf("%d %d %d\n",x,src,deep);
if(src=http://www.mamicode.com/=x)"%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&to[i]);
fromcnt[to[i]]+=1;
}
for(int i=1;i<=n;i++)
if(fromcnt[i]==0)
NaOH(i);
for(int i=1;i<=n;i++)
if(dev[i]==0&&d[i]==-1)
dfs(to[i],i,1);
printf("%d\n",ans);
return 0;
}
2
2
[NOIP2015]信息传递