小朋友崇拜圈 C++/C
题目描述
班里 NN 个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。
在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人？
小朋友编号为 1,2,3,\cdots N1,2,3,⋯N。
输入描述
输入第一行，一个整数 N（3<N<10^5）N（3<N<10
5
）。
接下来一行 NN 个整数，由空格分开。
输出描述
要求输出一个整数，表示满足条件的最大圈的人数。
输入输出样例
示例
输入
9
3 4 2 5 3 8 4 6 9
copy
输出
4
copy
样例解释
如下图所示，崇拜关系用箭头表示，红色表示不在圈中。
显然，最大圈是[2 4 5 3] 构成的圈。
运行限制
最大运行时间：1s
最大运行内存: 256M
#include<bits/stdc++.h> using namespace std; int n,cnt,ans; int a[100005]; void dfs(int x,int ll,int cnt){ if(cnt>n)return; //如果所有小朋友都搜索了，返回 if(x==ll){ //如果搜到了第一个传进来的小朋友，这个有向连通图就全部找完了 ans=max(ans,cnt); //更新答案 return; //记得一定return，不然死循环（虽然第一个return已经阻止了死循环，但答案肯定是错的） } dfs(a[x],ll,cnt+1); //搜索当前小朋友的崇拜对象 } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ dfs(a[i],i,1); //搜索每个小朋友崇拜的对象，并传入这个小朋友的编号 } cout<<ans; return 0; } //这种是针对每一个小朋友都进行DFS，但是这样时间复杂度为n^2 //这个是别人写的感觉时间复杂度有点大
这个是我自己写的优化的版本
#include<iostream> #include<cstring> using namespace std; #define N 100000 struct Student //定义一个结构体，love表示崇拜的人，flag有两个用途1.标志在dfs的时候是否已经搜索过，2.用于判断是属于从哪一个结点开始的 { int love; int flag; }; int n; int ans; int cnt; int view[N];//用于保存从某一个结点开始dfs要经过几次循环到这个结点 Student a[N]; void dfs(int x,int res) { a[x].flag=res; view[x]=++cnt;//存入循环到本结点需要用到的次数 int y=a[x].love; if(a[y].flag == res)//flag的第二个用途 { ans = max(ans,view[x]-view[y]+1); return; } else { dfs(y,res);//进行dfs搜索 } } int main() { cin >> n; memset(a,0,sizeof(a));//初始化为0 // cout << a[1000].flag<<a[1000].love; for(int i=1;i<=n;i++) { cin >> a[i].love; } for(int i=1;i<=n;i++) { if(!a[i].flag)//flag的第一个用途 { dfs(i,i); } } cout << ans; return 0; }
