【NOIP15 D1T2】信息传递

Source and Judge

NOIP2015 提高组 D1T2
Luogu2312
Caioj1568

Problem

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

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

Record

20min

Analysis

请先思考

一眼就是找最小环
如果直接暴力枚举是n方级别的
考虑题目特性,只有一条出边
显然所有强连通都是以环的形式出现的
找最小但至少有两个的强连通分量即可

Code

请先思考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
//*******************全局常量*******************
const int MAXN=210000;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
struct Nod
{
int hou;
int dfn,low;
bool v;
Nod()
{
hou=dfn=0;
v=0;
}
}p[MAXN];
struct Edge
{
int y,g;
}e[MAXN];
int ln=0;
void ins(int x,int y)
{
e[++ln]=(Edge){y,p[x].hou};p[x].hou=ln;
}
//*******************实现*******************
int id=0;
int sta[MAXN],top=0;
int siz[MAXN],cnt=0;
void tarjan(int x)
{
p[x].dfn=p[x].low=++id;
sta[++top]=x;p[x].v=1;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].dfn==0) tarjan(y);
if(p[y].v) p[x].low=mymin(p[x].low,p[y].low);
}
if(p[x].dfn==p[x].low)
{
cnt++;
while(1)
{
int t=sta[top--];
siz[cnt]++;
if(t==x) break;
}
}
}
//*******************主函数*******************
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int t;scanf("%d",&t);
ins(i,t);
}
for(int i=1;i<=n;i++) if(!p[i].dfn) tarjan(i);
int ans=INF;
for(int i=1;i<=cnt;i++) if(siz[i]>=2 and siz[i]<ans) ans=siz[i];
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-05/信息传递.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%