2283: 蓝桥杯2018年第九届真题-小朋友崇拜圈

解题思路:dfs

注意事项:一个人只能用一次

参考代码:

#include <iostream>
using namespace std;
int num[100005];
int flag[100005]={0};
int tong[100005]={0};//是否被崇拜 
int ans=0,n;
void dfs(int k,int x,int m){//k表示最开始的人，最后一个人崇拜的必须是他才能形成一个环
	if(k==num[x]){
		if(m>ans) ans=m;
		return;
	}
	flag[x]=1;
	if(flag[num[x]]==0){
		dfs(k,num[x],m+1);
	}
	flag[x]=0;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		tong[num[i]]=1;
	}
	for(int i=1;i<=n;i++){
		if(tong[i]==0) continue;//没有崇拜自己的，就形不成一个环，直接跳过 
		dfs(i,i,1);
	}
	cout<<ans;
    return 0;
}