我是靠谱客的博主 花痴八宝粥,这篇文章主要介绍[蓝桥杯][2018年第九届真题]小朋友崇拜圈(简单图论),现在分享给大家,希望可以做个参考。

题目描述
班里N个小朋友,每个人都有自己最崇拜的一个小朋友(也可以是自己)。
在一个游戏中,需要小朋友坐一个圈,
每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人?

小朋友编号为1,2,3,…N

输入
输入第一行,一个整数N(3<N<100000)
接下来一行N个整数,由空格分开。
输出
要求输出一个整数,表示满足条件的最大圈的人数。
样例输入
9
3 4 2 5 3 8 4 6 9
样例输出
4
思路:首先根据输入,建图。对于建好的图,我们的任务就是去找这个图中最大的环。首先我们将度为1的点去除掉之后,就直接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
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxx=1e5+100; struct edge{ int to,next; }e[maxx<<1]; int head[maxx<<1],deg[maxx],vis[maxx]; int n,tot; inline void init() { memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++) deg[i]=vis[i]=0; tot=0; } inline void add(int u,int v) { e[tot].to=v,e[tot].next=head[u],head[u]=tot++; } inline int dfs(int u,int num,int f) { if(vis[u]) return num; vis[u]=1; num++; for(int i=head[u];i!=-1;i=e[i].next) { int to=e[i].to; if(to==f) continue; return dfs(to,num,u); } } int main() { scanf("%d",&n); int x; init(); for(int i=1;i<=n;i++) { scanf("%d",&x); add(i,x); deg[i]++;deg[x]++; } queue<int> q;while(q.size()) q.pop(); for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i); while(q.size()) { int u=q.front(); q.pop(); deg[u]--; for(int i=head[u];i!=-1;i=e[i].next) { int to=e[i].to; deg[to]--; if(deg[to]==1) q.push(to); } } int _max=0; for(int i=1;i<=n;i++) { if(deg[i]&&vis[i]==0) { _max=max(_max,dfs(i,0,-1)); } } cout<<_max<<endl; return 0; }

努力加油a啊,(o)/~

最后

以上就是花痴八宝粥最近收集整理的关于[蓝桥杯][2018年第九届真题]小朋友崇拜圈(简单图论)的全部内容,更多相关[蓝桥杯][2018年第九届真题]小朋友崇拜圈(简单图论)内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(105)

评论列表共有 0 条评论

立即
投稿
返回
顶部