題目描述
班里N個(gè)小朋友，每個(gè)人都有自己最崇拜的一個(gè)小朋友（也可以是自己）。
在一個(gè)游戲中，需要小朋友坐一個(gè)圈，
每個(gè)小朋友都有自己最崇拜的小朋友在他的右手邊。
求滿足條件的圈最大多少人？

小朋友編號為1,2,3,…N

輸入
輸入第一行，一個(gè)整數(shù)N（3<N<100000）
接下來一行N個(gè)整數(shù)，由空格分開。
輸出
要求輸出一個(gè)整數(shù)，表示滿足條件的最大圈的人數(shù)。
樣例輸入
9
3 4 2 5 3 8 4 6 9
樣例輸出
4
思路：首先根據(jù)輸入，建圖。對于建好的圖，我們的任務(wù)就是去找這個(gè)圖中最大的環(huán)。首先我們將度為1的點(diǎn)去除掉之后，就直接dfs求出每一個(gè)環(huán)的長度，取最大值就可以了。
代碼如下：

#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)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][2018年第九届真题]小朋友崇拜圈（简单图论）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。