自动搬运

查看原文

来自洛谷，原作者为

	Deakin 你好 (^w^)/

搬运于2025-08-24 23:12:54，当前版本为作者最后更新于2025-04-16 20:48:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门

前言

本蒟蒻是初一学生，第一篇题解，我会尽可能用通俗易懂的语言来讲。 求通过 QAQ。

思路

第 $i$ 个传送门会传送到第 $a_i$ 个传送门。

根据题目对传送门的解释，我们发现这样就会形成一个循环（即经过一定次数的传送后会回到原点）的一条路径，这里统称为“环”。 （以例题来说，五个传送门 2, 1, 5, 4, 3 可以形成三个环：1→2、3→5、4）。 当进入到某一个环中，则可以到这个环中的任意一个传送门，且不用魔法。

同时他可以使用一次魔法，从某个传送阵 $j$ 走到相邻的（第 $j−1$ 或第 $j+1$ 个）传送阵。

其实本质上来说：从传送阵 $j$ 走到第 $j-1$ 个传送阵就相当于从第 $j-1$ 个传送阵走到传送阵 $j$。

所以，我们只需要从第 $1$ 个传送阵对应的环遍历到第 $n$ 个传送阵对应的环中找到相邻且不为同一个环的两个环和最多的传送阵数量。

到这里题目意思就很明确了，找出所有的独立环，并统计每个环的大小。找到传送门数量最多的两个相邻且不同的环。并输出这两个环中传送门数量之和。（注意有个坑：可能只有一个环）。 ‌

算法

思路实现

例题：

5
2,1,5,4,3

按照思路，先找出所有独立环，并统计大小。

预处理环结构

分析

数字	环节	节点数
$2$	$2→1→$	$2$
$1$	$1→2→$
$5$	$5→3→$
$4$	$4→$	$1$
$3$	$3→5→$	$2$

这里数字 $2$ 和数字 $1$ 在同一个环中，环大小也一样，却分别找了两次对应环。 很明显复杂了，改为直接继承能降低时间复杂度。 |数字|环节 |编号| 节点数 | |-----|----------|-----|------------| | $2$ | $2→1→$ | $1$ | $2$ | | $1$ | $1→2→$ | $1$ |同 $1$ | | $5$ | $5→3→$ | $3$ | $2$ | | $4$ | $4→$ | $4$ | $1$ | | $3$ | $3→5→$ | $3$ |同 $3$ |

继承的条件：在之前的某个环中有出现过。用数组 $id$ 的值的变化来表示有无出现过（出现过对 $id$ 做标记）。

判断继承：找对应环时对环中的数的 $id$ 进行处理。当处理过的数要找对应环时，找处理它 $id$ 的环的 $size$。

代码

先建立两个数组，帮助我们快速处理环结构。

int id[1000001];//id[]数组‌：标记每个节点所属的环编号(索引)。
‌int size[1000001];//size[]数组‌：记录每个环的节点数量。

找对应环

方法： 模拟传送，标记每个节点的所属编号和环节点数。

模拟传送： 遍历每个节点，若未被处理过，则通过模拟传送过程 i = a[i] 找到整个环，并标记其 $id$ 和计算 $size‌$。

int id[1000001]={0};//环的编号
int size[1000001]={0};//每个数对应环中传送阵的数量
//预处理每个环的id和size（类并查集）
for(int i=1;i<=n;i++){
  //如果i已经被处理过，直接取对应环的size
  if(id[i]!=0)size[i]=size[id[i]];
  else {
  int x=i;//环起点
  do{
      if(id[x]==0)id[x]=i;//标记环id
      size[i]++;//增加环的大小
      x=a[x];//模拟传送
    }while(x!=i);//当回到起点时结束循环
  }
}

求相邻环最大值

按照思路，找到传送门数量最多的两个相邻且不同的环。

继续以例题来说，先将预处理过的不同下标的环分开（比较直观）。

下标	编号	节点数
$1$		$2$
$2$	同 $id[1]$	同 $size[1]$
$3$		$2$
$4$		$1$
$5$	同 $id[3]$	同 $size[3]$

$id$ 不同肯定就是不同环，相邻且不同的环就相当于下标相邻值不同的两个环。（没有就找单个环最大）。

例题中有：$id[2]$ 和 $id[3]$，$id[3]$ 和 $id[4]$（或 $id[4]$ 和 $id[5]$）。 最多的就是 $id[2]$ 和 $id[3]$，所以输出：$4$。

代码

遍历所有相邻的环并计算这两个环中传送门数量之和（可能只有一个环）。

<相邻环求和>： 遍历每个节点 $i$，检查其与下一节点 $i+1$ 是否属于不同环： 若属于不同环（即 $id$ 不同），用魔法后的传送门数为两环的 $size$ 之和。

记录所有可能的和结果中的最大值‌。

int max=0;
for(int i=1;i<=n;i++){
  int m=size[id[i]];//当前i所在环的大小
  //如果i和i+1属于不同的环，计算合并后的总大小
  if(id[i]!=id[i+1])m+=size[id[i+1]];//使用魔法
  if(m>max)max=m;//计算最大值
}

完整代码

接下来看完整代码。

#include<iostream>
using namespace std;
int a[1000001];
int id[1000001]/*环的编号*/,size[1000001]/*每个数对应环中传送阵的数量*/;
int main(){
    int n,max=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    //预处理每个环的id和size（类并查集）
    for(int i=1;i<=n;i++){
        if(id[i]!=0)size[i]=size[id[i]];//如果i已经被处理过，直接取对应环的size
        else {
            int x=i;//环起点
            do{
                if(id[x]==0)id[x]=i;//标记环id
                size[i]++;//增加环的大小
                x=a[x];//模拟传送
            }while(x!=i);//当回到起点时结束循环
        }
    }
    for(int i=1;i<=n;i++){
        int m=size[id[i]];//当前i所在环的大小
        if(id[i]!=id[i+1])m+=size[id[i+1]];//如果i和i+1属于不同的环，计算合并后的总大小
        if(m>max)max=m;//计算最大值
    }
    printf("%d",max);
    return 0;
}

总结

我应该是最优题解吧（^w^）求赞。

复杂度分析

时间复杂度‌：$O(n)$。预处理和遍历均为线性操作。

空间复杂度‌：$O(n)$。需存储 $id$ 和 $size$ 数组。

代码复杂度：该算法通过‌并查集思想‌快速标记环结构，再通过遍历相邻节点尝试合并环，最终找到最大可能的环规模。代码简洁高效。

正确性分析

评测记录

‌ ‌环的标记‌： 预处理时，每个环的起点被设为唯一 $id$，环内所有节点的 $id$ 指向该起点，确保环的正确划分。

‌合并逻辑：遍历所有相邻节点，若属于不同环则合并，覆盖所有可能的魔法使用位置。