OPPO · 图 · 算法编程题
OPPO 图 n ≤ 1e3 时限 1 秒 / 256 MB

题目描述

给定一棵树，每个节点有一个权值。现在每次可以交换任意两个节点的权值，请问最少多少次交换可以使得每个节点的权值等于它的编号？
保证给出的权值是一个排列，也就是说保证一定有解。

输入输出

输入描述
第一行输入一个正整数 n ，代表树上的节点数量。
第二行输入 n 个正整数 a_i ，第 i 个正整数 a_i 是 i 号节点的权值， a_i 互不相同。
接下来的 n-1 行，每行输入两个正整数 u 和 v ，代表 u 号节点和 v 号节点有一条边相连。
2≤ n ≤ 1000
1≤ u,v,a_i ≤ n
输出描述
一个整数，代表最小的交换次数。

样例共 1 组

样例 1 · 第一次交换1号节点和2号节点的权值，四个点的权值变成[1,2,4,3] 第二次交换3号节点和4号节点的权值，四个点的权值变成[1,2,3,4]
输入
4
2 1 4 3
1 2
2 3
2 4
输出
2

算法解析依据充分

考点：图

数据规模 n ≤ 1e3 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e3
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：图

本题切入点

答案是「置换环数」的经典问题：最少交换次数 = n − 置换中环的个数。树结构只是干扰信息。

把关系抽象成点与边，再按问的类型选遍历/最短路/连通性算法。

思路框架（图 通法 · 非本题专属）

  1. 建图：邻接表（稀疏）或邻接矩阵（稠密）。
  2. 问「最少几步 / 最短路径」且边权为 1 → BFS。
  3. 问「是否连通 / 需要加几条边连通」→ 并查集 / 连通块计数。
  4. 问「带权最短路」→ Dijkstra（非负权）或 Floyd（点数小、多源）。
  5. 问「依赖顺序」→ 拓扑排序。

实现要点：注意是有向图还是无向图，无向图加边记得双向。

复杂度：时间 O(V+E) 遍历 / O(E log V) Dijkstra ｜ 空间 O(V+E)

该范式的通法易错点

  • 无向图只加了单向边。
  • BFS 入队时没标记访问，导致重复入队。

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。

样例解读

样例 1：输入 4 / 2 1 4 3 / 1 2 / 2 3 / 2 4 → 输出 2

第一次交换1号节点和2号节点的权值，四个点的权值变成[1,2,4,3]

第二次交换3号节点和4号节点的权值，四个点的权值变成[1,2,3,4]

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年OPPO秋招后端岗笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解