题目

并查集路径压缩动画演示

手动演示

分布式队列

解题思路

核心观察：可见性由“最慢副本”决定

题目规定：一个元素只有在主节点和所有副节点都同步完成后，才具有可见性。

换句话说：

当前可见的元素数量 = 所有节点（包括主节点）中已同步元素数量的最小值。

因为只要有一个节点还没同步到第 k 个元素，那么第 k 个元素就不可见。

操作含义转化为计数

• add：主节点（编号 0）的元素数量 +1。
• sync id：副节点 id 尝试同步下一个缺失元素，即 cnt[id]++，但不能超过主节点当前总数（防止过度同步）。
• query：输出 min(cnt[0], cnt[1], ..., cnt[n-1])。

注意：我们不需要存储具体元素值，只需维护每个节点当前同步了多少个元素。

边界处理：同步不能超过主节点

副节点同步时，必须保证：

cnt[id] = min(cnt[id] + 1, cnt[0])

这样即使多次对同一个副节点 sync，也不会让它“超前”于主节点。

输入终止：使用 hasNext() 判断 EOF

题目未给出操作总数，需持续读取直到文件结束。
在 Java 中，sc.hasNext() 在遇到 EOF（如本地 Ctrl+D 或在线评测输入结束）时返回 false，自然退出循环。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 节点总数, 0 为主节点, 1~n-1 为副节点
        // cnt[i] 表示节点 i 当前已同步的元素个数
        int[] cnt = new int[n];
        while (sc.hasNext()) {
            String op = sc.next();
            switch (op) {
                case "add":
                    // 添加元素: 只增加主节点计数, 不关心具体数值
                    sc.nextInt(); // 读掉 element, 但不用
                    cnt[0]++;
                    break;
                case "sync":
                    // 同步操作: 指定副节点尝试同步下一个元素
                    int id = sc.nextInt();
                    // 同步后不能超过主节点当前总数
                    cnt[id] = Math.min(cnt[id] + 1, cnt[0]);
                    break;
                case "query":
                    // 查询: 可见元素数 = 所有节点同步数量的最小值
                    int minCnt = Integer.MAX_VALUE;
                    for (int i = 0; i < n; i++) {
                        minCnt = Math.min(minCnt, cnt[i]);
                    }
                    System.out.println(minCnt);
                    break;
            }
        }
    }
}

最大开支

解题思路（贪心 + 优先队列解法）

核心观察：最坏情况 = 最大总花费

题目问的是：“小蓝至少要准备多少钱，才能应对所有人任意选择项目的情况”。

这等价于：在所有可能的人员分配方案中，找出总门票费用最大的那种情况。
因为只要能 cover 最坏情况（花得最多的情况），就一定能 cover 所有其他情况。

所以问题转化为：如何分配 N 个人到 M 个项目，使得总花费最大？

门票函数的性质

每个项目的单价为：max(K_i * X + B_i, 0)，其中 K_i < 0，所以：

• 随着人数 X 增加，单价单调下降。
• 当 K_i * X + B_i <= 0 时，单价为 0，再多人也不花钱。

但注意：总花费 = 单价 × 人数，不是单价本身！
虽然单价在降，但人数在增，总花费可能先升后降。

关键突破：考虑“新增一个人”的边际收益

我们不直接决定每个项目分多少人，而是一个一个地安排人，每次把当前这个人安排到“能让总花费增加最多”的项目里。

这就是贪心思想：每一步都做当前看起来最好的选择。

对于项目 i，如果已经有 x 个人，那么再加第 x+1 个人带来的新增花费为：

新总花费 - 旧总花费
= max(K_i*(x+1)+B_i, 0) * (x+1) - max(K_i*x+B_i, 0) * x = k_i(2x_i - 1)+b

这个值就是“边际贡献”。我们每次都选边际贡献最大的项目来加人。

💡 小技巧：因为 K_i < 0，随着 x 增大，这个边际贡献会越来越小（甚至变负或零）。所以每个项目“越往后加人，越不划算”。

为什么贪心是对的？

想象你是游乐园老板，想赚最多钱。你会怎么安排？

• 第一个人肯定去“单人票价最高”的项目。
• 第二个人呢？不能只看单价，要看“加他之后总钱变多多少”。
• 因为每个项目的边际收益是递减的，所以永远优先选当前收益增量最大的，不会错过更优解。

不需要复杂证明，记住口诀：“收益递减，贪心最优”。

实现工具：优先队列（最大堆）

用优先队列维护每个项目“如果现在加一个人，能多赚多少钱”。

初始时，每个项目加第 1 个人的收益是多少，先全放进去。
然后循环 N 次：

1. 取出收益最大的项目；
2. 如果收益 ≤ 0，说明再加人不赚钱了（甚至免费），后面的人都不用加了（因为收益只会更小）；
3. 否则，累加这笔收益，并更新该项目“下一个人”的边际收益，重新放回堆中。

参考代码

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 总人数
        int m = sc.nextInt(); // 项目个数
        int[] K = new int[m + 5];
        int[] B = new int[m + 5];
        for (int i = 1; i <= m; i++) {
            K[i] = sc.nextInt();
            B[i] = sc.nextInt();
        }
        // 最大堆：按“新增一个人带来的花费增量”从大到小排序
        // 数组内容: [新增花费, 项目编号, 加入后的人数]
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
        // 初始化：每个项目加入第1个人的新增花费
        for (int i = 1; i <= m; i++) {
            long nextCost = calCost(1, i, K, B);
            pq.offer(new long[]{nextCost, i, 1});
        }

        long totalCost = 0;
        // 依次安排每个人
        for (int person = 0; person < n; person++) {
            long[] top = pq.poll();
            long cost = top[0]; // 这个人加入带来的新增花费
            int projectId = (int) top[1];
            long cnt = top[2];  // 加入后该项目的人数
            if (cost <= 0) {
                // 如果新增花费 <= 0，说明再加人不会增加总花费
                break;
            }

            totalCost += cost;
            // 计算该项目当前总花费（用于后续计算增量）
            long currentCost = calCost(cnt, projectId, K, B);
            // 下一个人加入后的人数
            cnt++;
            // 下一个人加入后的总花费
            long nextCost = calCost(cnt, projectId, K, B);
            // 新增的花费 = nextTotal - currentTotal
            // 把更新后的项目信息放回堆中
            pq.offer(new long[]{nextCost - currentCost, projectId, cnt});
        }
        System.out.println(totalCost);
    }

    /**
     * 计算某个项目在指定人数下的总花费
     *
     * @param cnt 人数
     * @param id  项目编号
     * @param K   系数数组
     * @param B   基础值数组
     * @return 总花费 = max(K[id] * count + B[id], 0) * count
     */
    private static long calCost(long cnt, int id, int[] K, int[] B) {
        // 单价 * 人数
        return Math.max(K[id] * cnt + B[id], 0) * cnt;
    }
}

冷热数据队列

解题思路(模拟 · 基于 LinkedHashMap 的高效实现)

核心观察：需要支持快速查找、插入和按访问顺序淘汰

题目要求维护两个队列：

• 热队列 q₁：存放最近被重复访问的数据页，容量为 n1。
• 冷队列 q₂：存放首次访问的数据页，容量为 n2。

关键操作包括：

• 判断某数据页是否在任一队列中（需 O(1) 查找）。
• 将数据页移动到队首（即“最新”位置）。
• 队列满时从尾部（最旧）淘汰元素。

这正是 LRU（Least Recently Used）缓存的变种，而 Java 中没有像 C++ 那样能直接通过迭代器 O(1) 删除链表节点的机制。但我们可以借助 LinkedHashMap 巧妙实现。

为什么选择 LinkedHashMap？

LinkedHashMap 是一个哈希表 + 双向链表的结构，具备以下特性：

• O(1) 插入、删除、查找（继承自 HashMap）。
• 维护插入顺序：默认按“插入先后”排序，最早插入的在前，最新在后。
• 虽然不能直接访问“尾部”，但我们可以通过 keySet().iterator().next() 获取第一个（即最旧）的键。

💡 提示：map.keySet().iterator().next() 返回的是 LinkedHashMap 中第一个插入的 key，也就是逻辑上的“队尾”（最久未用），正好用于淘汰。

操作流程梳理

1. 读入数据页 num。
2. 检查是否已在热/冷队列中：
   • 如果在，先从原队列中删除（确保唯一性）。
3. 分情况处理：
   • 首次出现：加入冷队列；若冷队列超容，淘汰最旧元素。
   • 已存在过：加入热队列；若热队列超容，淘汰最旧元素，并将其移入冷队列首部。
4. 输出时注意顺序：
   • 题目要求输出“从新到旧”，而 LinkedHashMap 默认是“旧到新”，所以需逆序输出。

额外知识点：LinkedHashMap 关键 API 解释

• map.containsKey(key)：判断是否存在。

• map.remove(key)：O(1) 删除。

• map.put(key, value)：插入到末尾（最新位置）。

• map.keySet().iterator().next()：获取第一个（最旧）的 key。

  • keySet() 返回所有 key 的集合。
  • iterator() 获取迭代器。
  • next() 取第一个元素（因为 LinkedHashMap 有序，第一个就是最早插入的）。

这个技巧是本题在 Java 中高效实现的核心！

参考代码

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n1 = sc.nextInt(); // 热队列容量
        int n2 = sc.nextInt(); // 冷队列容量
        int m = sc.nextInt();  // 操作次数
        // 使用 LinkedHashMap 模拟有序队列
        // Boolean 值无实际意义, 仅占位；关键是利用其有序性和 O(1) 操作
        LinkedHashMap<Integer, Boolean> hotQueue = new LinkedHashMap<>();
        LinkedHashMap<Integer, Boolean> coldQueue = new LinkedHashMap<>();
        while (m-- > 0) {
            int num = sc.nextInt();

            // 检查当前数据页是否已在热队列或冷队列中
            boolean inHot = hotQueue.containsKey(num);
            boolean inCold = coldQueue.containsKey(num);
            // 无论在哪, 先彻底移除（保证唯一性）
            if (inHot) hotQueue.remove(num);
            if (inCold) coldQueue.remove(num);

            if (!inHot && !inCold) {
                // 第一次见啊, 进冷队列
                coldQueue.put(num, true);
                if (coldQueue.size() > n2) {
                    // 若冷队列超容, 淘汰最旧元素（第一个插入的）
                    int first = coldQueue.keySet().iterator().next();
                    coldQueue.remove(first);
                }
            } else {
                // 老朋友, 进热队列
                hotQueue.put(num, true);
                if (hotQueue.size() > n1) {
                    // 若热队列超容, 淘汰最旧元素, 并移入冷队列
                    int evict = hotQueue.keySet().iterator().next();
                    hotQueue.remove(evict);
                    // 直接放, 不需要考虑冷队列会满, 因为刚刚从冷队列扔了一个, 肯定有位置
                    coldQueue.put(evict, true);
                }
            }
        }
        // 输出两个队列: 从新到旧（逆序）
        printReverse(hotQueue);
        printReverse(coldQueue);
    }

    // 辅助函数：逆序打印 LinkedHashMap 的 key（从最新到最旧）
    static void printReverse(LinkedHashMap<Integer, Boolean> map) {
        List<Integer> keys = new ArrayList<>(map.keySet());
        for (int i = keys.size() - 1; i >= 0; i--) {
            System.out.print(keys.get(i) + " ");
        }
        System.out.println();
    }
}

左移右移

解题思路(基于虚拟顺序标记的高效解法)

核心观察：只需维护元素的相对顺序，无需真实移动

题目要求多次将某个元素移到最左或最右，最终输出整个数组。
如果直接模拟（如用 ArrayList 删除再插入），每次操作是 O(N)，总复杂度 O(MN)，在 N, M ≤ 200000 时会超时。

但注意：我们只关心最终顺序，不关心中间过程。因此可以为每个元素分配一个“虚拟顺序值”，通过调整这个值来表示其在序列中的相对位置。

• 初始时，元素 i 的顺序值设为 i。
• 每次 左移 x：将 x 的顺序值设为比当前最小值还小（如 --left）。
• 每次 右移 x：将 x 的顺序值设为比当前最大值还大（如 ++right）。

最后按“顺序值”从小到大排序，即可得到最终数组。

💡 “左减右加，排序即答” —— 不动数组，只改权重，一次排序搞定。

为什么这样可行？

因为：

• 所有左移操作产生的顺序值都小于初始值（1~N）。
• 所有右移操作产生的顺序值都大于初始值。
• 后执行的左移比先执行的更靠左（因为 left 递减），同理右移也满足后执行更靠右。
• 排序天然保证了这种偏序关系。

这种方法将每次操作降为 O(1)，总复杂度 O(N log N)，轻松通过大数据。

备选方案：双向链表 + 哈希定位

另一种思路是手动实现带哈希索引的双向链表：

• 链表支持 O(1) 删除和头/尾插入。
• 哈希表 pos 存储每个值对应的节点指针，实现 O(1) 查找。

虽然理论上也是 O(M)，但常数较大，代码复杂，且 Java 无内置支持（LinkedHashMap 无法任意插入到头部/尾部并保持全局顺序）。因此虚拟顺序标记法更简洁高效。

参考代码

方法一：虚拟顺序标记（推荐）

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        // nums[i][0] 存元素值, nums[i][1] 存其虚拟顺序值
        int[][] nums = new int[n + 5][2];
        for (int i = 1; i <= n; i++) {
            // 初始顺序值等于自身
            nums[i][0] = nums[i][1] = i;
        }
        // left 和 right 动态扩展顺序值范围
        int left = 1;   // 下一个左移元素的顺序值将设为 --left
        int right = n;  // 下一个右移元素的顺序值将设为 ++right
        while (m-- > 0) {
            String op = sc.next();
            int num = sc.nextInt();
            switch (op) {
                case "L":
                    // 左移: 顺序值设为比当前最小还小
                    nums[num][1] = --left;
                    break;
                case "R":
                    // 右移: 顺序值设为比当前最大还大
                    nums[num][1] = ++right;
                    break;
            }
        }
        // 按虚拟顺序值升序排序, 得到最终数组
        Arrays.sort(nums, 1, n + 1, Comparator.comparingInt(a -> a[1]));
        for (int i = 1; i <= n; i++) {
            System.out.print(nums[i][0] + " ");
        }
    }
}

方法二：双向链表 + 哈希定位（备选）

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        MyLinkedList list = new MyLinkedList();
        // 初始化双向链表
        for (int i = 1; i <= n; i++) {
            list.addLast(i);
        }
        while (m-- > 0) {
            String op = sc.next();
            int num = sc.nextInt();
            switch (op) {
                case "L":
                    // 把num提到最左边
                    list.remove(num);
                    list.addFirst(num);
                    break;
                case "R":
                    // 把num提到最右边
                    list.remove(num);
                    list.addLast(num);
                    break;
            }
        }
        // 遍历链表输出
        MyLinkedList.ListNode head = list.head;
        while (head.next != list.tail) {
            System.out.print(head.next.val + " ");
            head = head.next;
        }
    }
}

// 带哈希索引的双向链表
class MyLinkedList {
    static class ListNode {
        int val;
        ListNode next;
        ListNode pre;

        public ListNode(int val) {
            this.val = val;
        }
    }

    ListNode head;
    ListNode tail;
    // 值到节点的映射
    Map<Integer, ListNode> pos = new HashMap<>();


    public MyLinkedList() {
        head = new ListNode(0);
        tail = head;
        head.next = tail.pre = head;
    }

    // 在链表尾部添加元素
    public void addLast(int val) {
        // 先创建新节点
        ListNode node = new ListNode(val);
        // 插入到tail前面
        node.pre = tail.pre;
        node.next = tail;
        node.pre.next = node;
        node.next.pre = node;
        // 更新pos
        pos.put(val, node);
    }

    // 在链表头部添加元素
    public void addFirst(int val) {
        // 先创建新节点
        ListNode node = new ListNode(val);
        // 插入到head后面
        node.pre = head;
        node.next = head.next;
        node.pre.next = node;
        node.next.pre = node;
        // 更新pos
        pos.put(val, node);
    }

    // 删除指定值的节点
    public void remove(int val) {
        // 获取节点
        ListNode node = pos.get(val);
        // 删除
        node.pre.next = node.next;
        node.next.pre = node.pre;
        // 更新pos(其实也不用, 因为后面一定会再次插入并更新)
        pos.remove(val);
    }
}

聚合一块

解题思路(并查集统计连通分量数)

核心观察：答案 = 连通分量数量 - 1

题目要求最少加多少条边，使整张图变成一个连通块。

关键结论：

若当前图中有 k 个连通分量，则至少需要添加 k - 1 条边才能将它们全部连接成一个整体。

这是因为每加一条边最多只能合并两个连通分量，所以从 k 个变成 1 个，恰好需要 k - 1 次合并。

因此，问题转化为：统计初始图中有多少个连通分量。

为什么用并查集？

• 图中只有无向边，且只关心“是否连通”，不关心路径细节。
• 并查集（Union-Find）天然支持：
  • 快速判断两点是否在同一集合（通过 find）。
  • 合并两个集合（通过 merge 或 union）。
  • 动态维护连通分量总数。

初始时每个点自成一个连通分量（共 n 个）。
每读入一条边 (u, v)，若 u 和 v 不在同一集合，就合并它们，并将连通分量数减 1。

最终答案就是 连通分量数 - 1。

提示：避免术语障碍

未学过图论的同学，可以这样类比：

• 每个点是一个“人”，边是“朋友关系”。
• 连通分量就是“朋友圈”——圈内任意两人可通过朋友链认识。
• 问：最少介绍多少对新朋友，能让所有人变成一个大朋友圈？
• 答：有几个朋友圈，就介绍“朋友圈数 - 1”对。

参考代码

import java.util.Scanner;

public class Main {
    static int[] parent; // parent[i] 表示 i 的父节点
    static int size;     // 当前连通分量的数量

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 点数
        int m = sc.nextInt(); // 边数
    
        // 初始化并查集：每个点独立成一个集合
        parent = new int[n + 1];
        size = n; // 初始有 n 个连通分量
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    
        // 处理每条边
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            merge(u, v); // 尝试合并 u 和 v 所在的集合
        }
    
        // 最少需要 (连通分量数 - 1) 条边才能连成一个整体
        System.out.println(size - 1);
        sc.close();
    }
  
    // 路径压缩的 find 操作：找到 x 的根节点
    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        parent[x] = find(parent[x]); // 路径压缩，提升后续查询效率
        return parent[x];
    }
  
    // 合并 x 和 y 所在的集合
    private static void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY; // 合并两个集合
            size--;                // 连通分量总数减一
        }
        // 如果 rootX == rootY，说明已在同一连通分量，无需操作
    }
}

合根植物

解题思路(二维网格连通性统计)

核心观察：本质仍是连通分量计数

本题看似是二维网格问题，但输入直接给出了哪些格子已经“合根”（即连通），因此无需考虑网格结构本身如何建边。

• 总共有 m × n 个格子，初始时每株植物独立，即有 m × n 个连通分量。
• 每给出一条合根关系 (a, b)，就相当于在图中添加一条无向边。
• 最终答案就是剩余的连通分量数量。

这与上一题“最少加几条边使图连通”高度相似，只是本题不需要输出 size - 1，而是直接输出 size。

为什么不用处理二维坐标？

题目已将格子编号为 1 到 m×n（按行优先顺序），所有输入的合根关系也直接使用这个编号。
因此我们可以完全忽略二维结构，把问题当作一个普通的无向图连通性问题处理。

💡 提示：本题强调“问题抽象”的能力——无论原始场景是网格、树还是社交网络，只要能转化为“点与边”，并查集就能派上用场。

并查集的作用

• 初始化：每个编号自成一个集合。
• 对每条合根关系，尝试合并两个格子所在的集合。
• 若两者原本不在同一集合，则合并后总连通分量数减 1。
• 最终 size 即为合根植物的株数（每株对应一个连通块）。

参考代码

import java.util.Scanner;

public class Main {
    // parent[i] 表示编号 i 的格子所属集合的根节点
    static int[] parent;
    // 当前连通分量（即合根植物）的数量
    static int size;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(); // 行数
        int n = sc.nextInt(); // 列数
        int k = sc.nextInt(); // 合根关系数量
        // 初始化并查集：每个点独立成一个集合
        parent = new int[m * n + 5];
        // 初始每格一株, 共 m*n 株
        size = m * n;

        // 初始化并查集：每个格子独立
        for (int i = 1; i <= m * n; i++) {
            parent[i] = i;
        }

        // 处理每一条合根关系
        while (k-- > 0) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            // 合并 a 和 b 所在的植物（连通块）
            merge(u, v);
        }
        // 输出最终的合根植物数量（即连通分量数）
        System.out.println(size);
    }

    // 路径压缩的 find 操作：找到 x 的根节点
    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        parent[x] = find(parent[x]); // 路径压缩, 提升后续查询效率
        return parent[x];
    }

    // 合并 x 和 y 所在的集合
    private static void merge(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot) {
            // 如果 rootX == rootY, 说明已在同一连通分量, 无需操作
            return;
        }
        // 合并两个集合
        parent[xRoot] = yRoot;
        size--; // 连通分量总数减一
    }
}

传送阵

解题思路(基于并查集的环合并优化)

核心观察：排列构成若干独立环，魔法可连接相邻环

题目给出一个长度为 n 的排列 a，表示从第 i 个传送阵会传送到 a[i]。
由于是排列，每个点出度和入度均为 1，整个结构由若干个互不相交的环组成。

• 在不使用魔法时，小蓝一旦进入某个环，就只能在该环内循环，最多访问该环的所有节点。
• 使用一次魔法，可以从位置 j 走到 j-1 或 j+1（物理相邻），从而跳到另一个环。
• 因此，最优策略是：选择两个物理位置相邻的环，通过魔法将它们连通，总访问数 = 两环大小之和。

💡 关键突破口：魔法不能任意连接两个环，只能连接“在数组中下标相邻”的两个环。

算法设计：并查集 + 枚举相邻对

1. 构建环的连通分量：
   • 对每个 i，将 i 与 a[i] 合并（因为它们在同一环中）。
   • 并查集自动将每个环缩成一个连通分量，并记录其大小。
2. 计算答案：
   • 初始答案为最大单个环的大小（不用魔法的情况）。
   • 枚举所有相邻位置对 (i, i+1)：
     • 若它们属于不同连通分量，则考虑合并后的大小 size[find(i)] + size[find(i+1)]。
     • 更新最大值。

⚠️ 注意：我们不实际执行合并，只是查看“如果连接这两个分量能得到多大”，因为魔法只能用一次。

为什么并查集适合？

• 自然支持“环内连通”建模。
• 支持 O(α(n)) 的查找与合并。
• 可高效维护每个连通分量的大小。

参考代码

import java.util.Scanner;

public class Main {
    // parent[i] 表示 i 所在集合的根节点
    static int[] parent;
    // size[i] 表示以 i 为根的集合的元素个数
    static int[] size;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 初始化并查集
        parent = new int[n + 5];
        size = new int[n + 5];
        int[] next = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            next[i] = sc.nextInt();
            parent[i] = i;
            size[i] = 1;
        }

        // 构建环: 将每个 i 与其传送目标 a[i] 合并
        for (int i = 1; i <= n; i++) {
            merge(i, next[i]);
        }
        // 初始答案: 最大单个环的大小(不用魔法的情况)
        int maxSize = 0;
        for (int i = 1; i <= n; i++) {
            maxSize = Math.max(maxSize, size[i]);
        }
        // 枚举所有物理相邻的位置对 (i, i+1), 尝试用魔法连接
        for (int i = 1; i < n; i++) {
            int root1 = find(i);
            int root2 = find(i + 1);
            if (root1 != root2) {
                maxSize = Math.max(maxSize, size[root1] + size[root2]);
            }
        }
        // 输出最大连通分量大小
        System.out.println(maxSize);
    }

    // 路径压缩的 find 操作: 找到 x 的根节点
    private static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩, 提升后续查询效率
        }
        return parent[x];
    }

    // 按大小合并(带秩合并)
    private static void merge(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        // 如果 rootX == rootY, 说明已在同一连通分量, 无需操作
        if (xRoot == yRoot) return;
        // 按秩合并
        if (size[xRoot] < size[yRoot]) {
            parent[xRoot] = yRoot;
            size[yRoot] += size[xRoot];
        } else {
            parent[yRoot] = xRoot;
            size[xRoot] += size[yRoot];
        }
    }
}