2016年蓝桥杯省赛B组交换瓶子题解（洛谷P8637）| 解题思路与代码优化

一、题目解读

题目要求将N个瓶子通过交换操作使其编号与位置对应（即每个瓶子指向自身）。每个瓶子初始指向另一个瓶子位置，需计算最小交换次数。例如，当瓶子i指向瓶子j时，交换i与j的位置可使两者指向自身。题目关键在于识别环形结构并计算交换次数。

二、解题思路

并查集（Union-Find）思想优化解题：

1. 将每个瓶子视为节点，初始各节点自成环。

2. 遍历时标记已访问节点，识别出每个连通环（即闭合路径）。

3. 每个环的交换次数为环大小-1（最后一个节点无需交换）。

4. 累加所有非单节点环的交换次数，得到最终结果。

核心在于利用环结构特性减少无效交换计算。

三、解题步骤

1. 输入处理：读取N及每个瓶子的指向位置，存储于bottles数组（1-based索引）。

2. 初始化标记：使用visited数组记录节点是否被遍历。

3. 循环遍历：

    对每个未访问节点i，启动新环遍历。

    通过while循环跟踪链i → bottles[i] →...直至回到起点（形成环）。

    标记路径上所有节点，记录环大小cycleSize。

4. 交换次数计算：若环大小>1，则需cycleSize-1次交换（单节点环无需交换）。

5. 输出结果：累加所有环的交换次数并输出。

四、代码与注释

#include <iostream>
#include <vector>
using namespace std;

int main() {
   int N;
   cin >> N;
   vector<int> bottles(N + 1);  // 使用1-based索引
   vector<bool> visited(N + 1, false);
   
   // 读取输入
   for (int i = 1; i <= N; ++i) {
       cin >> bottles[i];
   }
   
   int swapCount = 0;
   
   // 遍历每个瓶子
   for (int i = 1; i <= N; ++i) {
       if (!visited[i]) {   // 未访问节点为新环起点
           // 开始一个新的环
           int current = i;
           int cycleSize = 0;
           
           // 遍历整个环
           while (!visited[current]) {
               visited[current] = true;  // 标记已访问
               current = bottles[current];  // 跟踪指向节点
               cycleSize++;              // 环大小+1
           }
           
           // 每个大小为k的环需要k-1次交换
           if (cycleSize > 1) {
               swapCount += (cycleSize - 1);
           }
       }
   }
   
   cout << swapCount << endl;
   return 0;
}

注释说明：

● visited数组用于避免重复遍历已处理的环。

● cycleSize记录当前环的节点数，通过累加遍历次数计算。

● 最终交换次数仅累加非单节点环的贡献，避免冗余计算。

五、总结

本解法通过并查集思想将问题转化为环计数，有效降低时间复杂度。关键在于识别闭合路径并优化交换次数计算逻辑。代码简洁且易于理解，适用于处理具有环形结构的交换问题。掌握此类算法思维对编程竞赛中复杂路径问题的解决具有重要价值。

参考：2016蓝桥杯省赛B组交换瓶子题解