AcWing
1224. 交换瓶子
暴力做法：每一个数都必须回到它自己的位置上，比如1必须在第一位，2必须在第二位上。那么就可以这样操作：由于每个数必须回到自己的位置，直接从 1枚举到n，如果当前位置的数不等于它的下标，就必须要把它给替换成下标这个数。设当前位置为i，从i+1开始往后枚举，直到找到对应的a[j]和i相等，交换这两个数，把交换次数++. 暴力做法的时间复杂度是$O(n^2)$.
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 10010;
int a[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
int res = 0;
for(int i = 1; i <= n; i ++){
if(a[i] == i) continue;
for(int j = i + 1; j <= n; j ++){
if(a[j] == i){
swap(a[i], a[j]);
res ++;
break;
}
}
}
cout << res;
return 0;
}
置换群做法：假如交换置换群中的一个边上的两个点，那么就会将一个置换群分为两个，且对其他置换群没有影响。最终的目标是，得到n个置换群，此处n是原序列的长度。所以，只需要找到原序列有多少个置换群cnt，需要交换的次数就是n-cnt. 置换群做法的时间复杂度为$O(n)$.
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 10010;
int a[N]; // 原数组
bool visited[N]; // 元素是否已经在某个置换群中
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
int cnt = 0; // 置换群的个数
for(int i = 1; i <= n; i ++){
if(!visited[i]){
cnt ++;
for(int j = i; !visited[j]; j = a[j])
visited[j] = true; // 标记置换群中所有的元素
}
}
cout << n - cnt;
return 0;
}