https://www.luogu.org/problemnew/show/P2661

C++版本一

并查集

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp,sum;
int pre[N];
int dist[N];
vector<int>G[N];
char str;
struct node{};
int find(int x){
    if(pre[x]!=x){
        int last=pre[x];
        //cout<<x<<" "<<pre[x]<<endl;
        pre[x]=find(pre[x]);
        dist[x]+=dist[last];
    }
    return pre[x];
}
void check(int a,int b){
    int tx=find(a);
    int ty=find(b);
    if(tx!=ty){
        pre[tx]=ty;
        dist[a]=dist[b]+1;
    }else{
        ans=min(ans,dist[a]+dist[b]+1);
    }
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    ans=INF;
    for(int i=1;i<=n;i++){
        pre[i]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&m);
        check(i,m);
    }
    cout<<ans<<endl;

    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：将每个同学当作一个结点，将每次传递当作一条有向的线，一轮游戏便可以看作是个图。

那么，不难发现，如果想要有一个同学说出的生日重新传回自己的耳中，图中必定有一个环（环中的每个结点互相可以连通）。

如果有一个同学无法从别人口中传到自己的生日，也能说明是在游戏中他的生日落入了一个循环，依旧是一个环，只不过环的结点不包括那个人罢了。既然要求最小的游戏轮数，也就是要求最小的环，楼上对于环的解析很清楚了。

我的思路是，从每个人开始，按照输入的信息，寻找环，如果有个环没有被找到，就打个标记（那个人的编号），如果环已经被打标记了，就不用多浪费时间复杂度了。然后，用得到的环的边数更新 x 最小值。预计时间复杂度为 O(n)。

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp,sum;
int a[N];
int dist[N];
int dp[N];
vector<int>G[N];
char str;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    ans=INF;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        dist[i]=1;
        int t=i;
        int p=a[i];
        while(dp[p]!=i){
            if(dp[p]&&dp[p]<i)
                break;
            dist[p]=dist[t]+1;
            dp[t]=i;
            t=p;
            p=a[t];
        }
        if(dp[p]==i&&ans>dist[t]-dist[p]+1)
            ans=dist[t]-dist[p]+1;
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}