?

原題連接：藍橋杯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;}