[蓝桥杯][2018年第九届真题]小朋友崇拜圈（简单图论）

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

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

输入
输入第一行，一个整数N（3<N<100000）
接下来一行N个整数，由空格分开。
输出
要求输出一个整数，表示满足条件的最大圈的人数。
样例输入
9
3 4 2 5 3 8 4 6 9
样例输出
4
思路：首先根据输入，建图。对于建好的图，我们的任务就是去找这个图中最大的环。首先我们将度为1的点去除掉之后，就直接dfs求出每一个环的长度，取最大值就可以了。
代码如下：

#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年第九届真题]小朋友崇拜圈（简单图论）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。