蓝桥杯2024年第十五届省赛真题-传送阵

#include <bits/stdc++.h>

using namespace std;

int n, a[1000010], vis[1000010] = { 0 }, cnt[1000010] = { 0 }, indx = 0,ans=0;
int solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            ++indx;
            vis[i] = indx;
            ++cnt[indx];
            int tmp = a[i];
            while (!vis[tmp])
            {
                vis[tmp] = indx;
                tmp = a[tmp];
                ++cnt[indx];
            }
        }
    }
    if (indx == 2)
    {
        return n;
    }
    for (int i = 2; i <= indx; ++i)
    {
        if (vis[i] != vis[i - 1]) {
            ans = max(ans, cnt[vis[i]] + cnt[vis[i - 1]]);
            
            /*我第一次写的时候错误地把循环内的部分写成：
            
            ans = max(ans,cnt[i]+cnt[i-1]);
            
            这样做是不对的，会错过一些本来能用魔法跳跃进行相加的环。
            */
            
        }
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << solve();
    return 0;
}