AcWing 1224 交换瓶子（简单图论）

[题目概述]

有 N 个瓶子，编号 1∼N，放在架子上。

比如有 5 个瓶子：

2 1 3 5 4

要求每次拿起 2 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

1 2 3 4 5

对于这么简单的情况，显然，至少需要交换 2 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式

第一行包含一个整数 N，表示瓶子数量。

第二行包含 N 个整数，表示瓶子目前的排列状况。

输出格式

输出一个正整数，表示至少交换多少次，才能完成排序。

数据范围

1 ≤ N ≤ 10000 , 1 ≤ N ≤ 10000, 1≤N≤10000,

输入样例1：

5
3 1 2 5 4

输出样例1：

3

输入样例2：

5
5 4 3 2 1

输出样例2：

2

我们可以将一个瓶子看成一个点，它与其正确位置上的瓶子序号连线就构成了图

拿样例画一下

正确位置：1 2 3 4 5

现在位置：3 1 2 5 4

现在第一个位置的3指向3号位置对应的2，然后2指向2号对应位置的1号瓶子，1指向1号位置对应的3号瓶子，这样先构成了第一个环；5指向5号位置的4号瓶子，4指向4号位置的5号瓶子。

现在我们需要交换顺序了

分为两种情况，同一个环内的两个点交换，不同环内的点交换

1.同一个环内的两个点交换

假设交换2和3

正确位置：1 2 3 4 5

现在位置：2 1 3 5 4

变成了3个环

2.不同环之间交换

假设交换1和5

正确位置：1 2 3 4 5

现在位置：3 5 2 1 4

两个环合成了一个环

理想状态是

正确位置：1 2 3 4 5

现在位置：1 2 3 4 5

也就是五个环，所以我们现在要增加3个环，也就是进行3次操作

那么原来有k个环，我们就要进行n-k次操作，现在就是要求一共有几个环。

• 完整代码

  #include 
  #include 
  #include 
  #include 
  #include 
  using namespace std;
  const int N = 10005;
  int b[N]; // 记录每个位置放的哪个瓶子
  bool st[N]; // 记录每个瓶子是否被用过（判断环）
  int n;
  int main() {
  	cin >> n;
  	for (int i = 1; i 
  		cin > b[i];
  	}
  	int k = 0;
  	for (int i = 1; i 
  		// 一个环的开始
  		if (!st[i]) {
  			k ++;
  			// 一个环接下来的所有点
  			// j的更新在下面解释
  			for (int j = i; !st[j]; j = b[j]) {
  				st[j] = true;
  			}
  		}
  	}
  	cout