自己写的纯暴力

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n;
int a[N];
int main()
{
    int ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] != i) {
            for (int j = i + 1; j <= n; j++) {
                if (a[j] == i) {
                    swap(a[j], a[i]);
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

y总写的置换群
置换群的思路，这题转换成图论。每个瓶子与他应该在的位置上的瓶子连一条线，会形成许多成环的图，这些图为置换群。
根据题意，每个点如果与自身成自环，则这个点的位置是正确的。
交换同一个群中的两个瓶子，会使得这个环裂开成两个环
交换不同群中的两个瓶子，会使得这两个环合并成一个环
所以初始状态为k个环的时候，最少经过n-k次操作使得他们变成n个环

#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 10010;
int a[N];
int vis[N];
int cnt;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cnt++;
            for (int j = i; !vis[j]; j = a[j]) {
                vis[j] = 1;
            }
        }
    }

    cout << n - cnt << endl;

    return 0;
}