+1 - 帖子

读完题，发现这题好像可以模拟。。。。刚开始我想记录一下每个人当前最新获得的信息，也就是追踪每一个人的生日信息这一轮会给到谁，进而统计什么时候会游戏结束代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n;
int fa[N],t[N],d[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i];
		d[i]=t[i];
	}
	int ans=0;
	while(++ans)
	{
		for(int i=1;i<=n;i++)
		{
			fa[i]=d[i];
		}
		for(int i=1;i<=n;i++)
		{
			d[i]=t[fa[i]];
		}
		for(int i=1;i<=n;i++)
		{
			if(fa[i]==i)
			{
				cout<<ans;
				return 0;
			}
		}
		if(ans>n)
		break;
	}
	return 0;
}

很不幸，TLE了两个点但暴力一次我怎么能甘心呢；于是我换了一个思路，我统计了当前一轮每个人新获得的信息，然后判断有没有下一个人的信息

#include<bits/stdc++.h>
using namespace std;
const int N=50000;
queue<int> que[N];
queue<int> g[N];
int n;
int t[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i];
		que[i].push(i);
	}
	int ans=0;
	while(++ans)
	{
		for(int i=1;i<=n;i++)
		while(!que[i].empty())
		{
			int a=que[i].front();
			que[i].pop();
			if(a==t[i])
			{
				cout<<ans;
				return 0;
			}
			g[t[i]].push(a);
		}
		for(int i=1;i<=n;i++)
		while(!g[i].empty())
		{
			int a=g[i].front();
			g[i].pop();
			que[i].push(a);
		}
		if(ans>n)
		return 0;
	}
}

但很可惜，这样写数组开大了会MLE/TLE，开小了又RE了最后有三个点过不去，拿了七十分；

所以说，不管什么题，先给它暴力了，暴力yyds！！！！

好了，言归正传，再读一遍题，你会发现这可以构成一张有向图；于是这道题就成了一个求最小环的题；那问题就简单了，用并查集统计一下下最小环就可以了：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n;
int mn;
int fa[N],dis[N];
int find(int x)
{
	if(x!=fa[x]){
		int t=fa[x];
		fa[x]=find(fa[x]);
		dis[x]+=dis[t];
	}
	return fa[x];
}
void check(int x,int y)
{
	int a=find(x);
	int b=find(y);
	if(a!=b){
		fa[a]=b;
		dis[x]=dis[y]+1;
	}
	else
	{
		mn=min(mn,dis[x]+dis[y]+1);
	}
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	mn=0x3f3f3f3f;
	for(int i=1;i<=n;i++)
	{
		int t;
		cin>>t;
		check(i,t);
	}
	cout<<mn;
	return 0;
}