并查集

n个传送阵可能会构成多个环，利用并查集把n个传送阵构造成若干个环，并让每个根节点记录对应环的长度。
最后遍历每个传送阵，判断当前传送阵和前后邻近的传送阵是否连通，不连通则说明可以使用魔法，将两个环的长度加起来；连通则说明在同一个环里。结果取最大值

#include <iostream>
using namespace std;
const int N = 1e6+2;
int n;
int fa[N];

void init()
{
  for(int i = 1;i<=n;i++)
   fa[i] = i;
}

int root(int x)
{
  return fa[x] = (x == fa[x]? x : root(fa[x]));
}

void add(int x ,int y)
{
  if(root(x) != root(y))
  {
    fa[root(x)] = root(y);
  }
}

int main()
{
  cin>>n;
  int next[n+1];
  int num[n+2] = {0};
  bool v[n+1] = {0};
  init();
  for(int i = 1;i<=n;i++)
  {
    cin>>next[i];
  }
  for(int i = 1;i<=n;i++)
  {
    if(v[i]) continue;
    v[i] = true;
    int now = i;
    int cnt = 1;
    while(next[now] != i)
    {
      add(now, next[now]);
      v[next[now]] = true;
      now = next[now];
      cnt++;
    }
    num[root(i)] = cnt;
  }
  int ans = 0;
  for(int i = 1;i<=n;i++)
  {
    if(root(i)!= root(i-1))
     ans = max(ans, num[root(i)] + num[root(i-1)]);
    if(root(i) != root(i+1))
     ans = max(ans, num[root(i)] + num[root(i+1)]);
  }
  cout<<ans;
  return 0;
}