Akira的OI(咸鱼)圈

[P2661]信息传递

Word count: 420 / Reading time: 2 min
2018/07/26 Share

这题的题意是将每个人及其信息传递对象抽象成一个有向图,最大传递次数即为最小环的长度。我们可以先用拓扑排序找环,显然的,不断拓扑后环上的每一个点的入度均不为零。因此我们可以用DFS求环的长度,访问过的点打上标记,不再求已经访问过的环的长度,以此降低时间复杂度。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define ll long long
#define maxn 1000001
using namespace std;
queue<int>q;
int n,to[maxn],Next[maxn],head[maxn],dg[maxn],ans=0x3f3f3f3f,t;
bool in[maxn],vis[maxn],f;
inline int read()
{
int l=0,w=1;
char ch=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
l=(l<<3)+(l<<1)+(ch^'0');
ch=getchar();
}
return w*l;
}
inline void dfs(int x)
{
t++;
for(int i=head[x];i!=-1;i=Next[i])
if(dg[to[i]])
if(!vis[to[i]])
vis[to[i]]=1,dfs(to[i]);
}
int main()
{
memset(head,-1,sizeof(head));
int u;
n=read();
for(int i=1;i<=n;i++)
{
u=read();
to[t]=u,Next[t]=head[i],head[i]=t++;
dg[u]++;
}
for(int i=1;i<=n;i++)
if(!dg[i])
q.push(i);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i!=-1;i=Next[i])
{
dg[to[i]]--;
if(!dg[to[i]])
q.push(to[i]);
}
}
for(int i=1;i<=n;i++)
if(dg[i]&&!vis[i])
{
t=0;
vis[i]=1,f=1;
dfs(i);
if(t)
ans=min(ans,t);
}
if(f)
printf("%d\n",ans);
else
printf("0\n");
return 0;
}

CATALOG