会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
思路
- 图建模：对每个位置 i，连无向边 (ai,bi)。则图的每个连通块中的所有值最终必须被“合并”为同一个值。
- 关键结论：若某连通块包含 k 个不同值，至少需要 k−1 次操作（每次操作最多将不同值的种类数减少 1），且可沿生成树依次合并达到该下界。
- 答案：设 K 为在 a∪b 中出现的不同值总数，C 为上述图的连通块个数，则最少操作数为
K−C.
实现用并查集（DSU）统计出现值的连通块个数即可。注意要把所有出现过的值计入节点，即便某值只与自己相连（如 ai=bi）。
