题解：P12123 [蓝桥杯 2024 省 B 第二场] 传送阵

这道题其实很简单的（结果考试没有做起......想到用并查集，但是忘记咋写了 qwq，模板和基本功很重要啊！）

题目大意

给出 n 个点之间的关系：每个点只指向一个下一个点，即每个点只有一个儿子（有可能是自己————自环）。问如何走能有最长路径，其中可以任意的从一个点跳到另一个点（无视限制）

思路

题意很简单，就是需要知道从哪个点开始走的最长路最长，其中可以任意的从一个点跳跃到另一个点，但是这个魔法只能使用一次。

• 到这里就很好想了，求出每个点能跑出的最长路，然后再将答案最大的两个点相加就是答案。 x 错误！
• 为什么错了？
  如果两个点在同一个环内，这样环内所有点的最长路长度有可能相同（例如 n-1 点形成一个环，然后第 n 个点是自环）
• 现在就很好想了，先跑一遍最长路，一遍并查集将环合并了，这时候的点就有两种情况———在某一个环内 / 是一个孤立点（其实也是一个自环），然后连接环内所有点到环的根节点。最后遍历一遍所有节点，将满足： 1. 不在同一个环内 2. 相邻的 两个点最长路和相加取最大值即可。

求最长路 Tip：

相信应该不会有可爱滴憨憨会在这道题用 SPFA，Dijsktra 等能跑最长路的算法来求最长路吧！那我问你，用这些算法如何处理特殊的那条边呢？（就算暴力枚举处理包会炸的！ O(n²) ）

所以很明显哈，因为每个点只有一个儿子，那么就不会出现走到一个点有多条路选择，同时这道题用的是并查集，那么可以在合并查找父亲点时为所有父节点 +1，那么我们就可以在处理并查集的同时计算出最长路

AC Code

#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

const int maxn = 1e6 + 5;

struct Edge {
    int u, v, next;
} e[maxn];

int n, a[maxn];
int ans, fa[maxn];
void Init() {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
}

int Find(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = Find(fa[x]);
}

void Input() {
    scanf("%d", &n);
    Init();
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        int root_a = Find(i), root_b = Find(a[i]);
        if (root_a != root_b) {                        //并查集模板：合并节点
            fa[i] = fa[a[i]];
        }
    }
    for (int i = 1; i <= n; ++i) {                    //额外再跑一遍让环内所有点直接连到根节点（个人代码风格，和题目无关）
        Find(i);                                    /*这样可以使fa[i]直接指向i的根节点，和 在用的时候再调用Find(i)一样滴~*/ 
    }
}

int Size[maxn];                                        //记录所有点的最长路长度 
void Sol() {
    for (int i = 1; i <= n; ++i) {                    //累加根节点的最长路长度 
        ++Size[fa[i]];
    }
    
    for (int i = 1; i <= n; ++i) {                    //先只计算最长路最大的单个环（不使用"魔法"） 
        ans = max(ans, Size[i]);
    }
    for (int i = 1; i < n; ++i) {                    //然后按照题目要求计算：最大相邻的两个环最长路的和 
        if (fa[i] != fa[i + 1]) {
            ans = max(ans, Size[fa[i]] + Size[fa[i + 1]]);
        }
    }
}

int main() {
    Input();
    Sol();
    printf("%d", ans);
    return 0;
}

注意：

题目中使用魔法有限制，只能从 j 直接跳到 j+1/j-1
但是由于本题数据极水，直接取最长路最大的两个环最长路之和就能过，希望加强数据，因为同学就那样 AC 了这道题......