蓝桥杯真题——传送阵

原题连接：蓝桥杯2024年第十五届省赛真题-传送阵 - C语言网

知识点：并查集 

题目描述

小蓝在环球旅行时来到了一座古代遗迹，里面并排放置了 n 个传送阵，进入第 i 个传送阵会被传送到第 ai 个传送阵前，并且可以随时选择退出或者继续进入当前传送阵。小蓝为了探寻传送阵中的宝物，需要选择一个传送阵进入，然后连续进入之后的传送阵。小蓝希望尽可能多地进入传送门以便搜索宝物，同时他可以使用一次魔法，从某个传送阵 j 走到相邻的（第 j − 1 或第 j + 1 个）传送阵，请问小蓝最多能到达多少个不同的传送阵？一个传送阵可多次进入，但在计算答案时只算一个。

输入格式

输入的第一行包含一个正整数 n 。第二行包含 n 个正整数 a1, a2, · · · , an ，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

5
2 1 5 4 3

样例输出

4

提示

【样例说明】

小蓝的路径可以是：1 → 2 → 3 → 5 。其中 2 → 3 使用魔法。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n ≤ 1000 ；对于所有评测用例，1 ≤ n ≤ 106，且 a 是 1 至 n 的一个排列。

详解：第十五届蓝桥杯省赛第二场C/C++B组C题【传送阵】题解_蓝桥杯2024年第十五届省赛真题-传送阵-CSDN博客

思路： 

 所有的传送阵是以一个环的形式存在

所有点出度都为1，即只能从这个点出发到达另外一个点
一个排列中ai出现的次数就是其入度
即最后一定是成一个环
即可构成n个有向连通图，且每个连通图都是一个环

先跑完一个环，再枚举所有使用魔法的结果

如何快速算出每个节点的节点数：并查集

主要步骤：

使用cnt[far[i]]来存放每个环内的节点个数
当使用魔法从x跳到y时，分别找到其祖先节点，判断其祖先节点是否相等，
若相等，即在同一个环中，不用再进行相加操作
若不同，可令far[x]=y，cnt[y]+=cnt[x]，实现两个环节点数相加（将x加到y） 

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring> 
#define int long long
using namespace std;

const int N=1000000+10;

int n;
int a[N];
int fa[N],cnt[N];//父节点，每个环的结点个数 
int ans;

void init()//并查集初始化 
{
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		cnt[i]=1;
	}
}
int findf(int x)
{
	if(fa[x]!=x)
		fa[x]=findf(fa[x]);
	return fa[x];
}
void union_(int x,int y)
{
	x=findf(x);
	y=findf(y);//找出父节点
	if(x!=y)
	{
		fa[x]=y;
		cnt[y]+=cnt[x];
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>n;
	init();//初始化 
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		//由题意可知i与a[i]具有环的关系，将两点相连，即指向同一父节点 
		union_(i,a[i]);//将能连接的节点相连，即造出m个环 
	}
	//已经通过union_函数将i与a[i]链接，在后面的操作中不再考虑位置问题 
	for(int i=1;i<n;i++)//使用魔法，即遍历i和i+1的点
	{
		ans=max(ans,cnt[findf(i)]);//不使用魔法时的节点数 
		if(findf(i)!=findf(i+1))//不同的环 
			ans=max(ans,cnt[findf(i)]+cnt[findf(i+1)]);
	 } 
	cout<<ans<<endl;
	return 0;
 }