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

本文主要是介绍AcWing 1224 交换瓶子（简单图论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[题目概述]

有 N 个瓶子，编号 1∼N，放在架子上。
比如有 5 个瓶子：
2 1 3 5 4
要求每次拿起 2 个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5
对于这么简单的情况，显然，至少需要交换 2 次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。

输入格式

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

输出格式

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

数据范围

$1 \leq N \leq 10000,$

输入样例1：

5
3 1 2 5 4

输出样例1：

输入样例2：

5
5 4 3 2 1

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