置换群

$O(n)$

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

int a[N], n;
bool st[N];

// 对于每个环，如果它含有0，则只需要交换cnt - 1次即可
// 若不含0，则先把0换进环里，再交换(cnt + 1) - 1次即可，共cnt + 1次

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(a[i] == i) continue; 
        if(!st[i]){
            int cnt = 0;
            bool flag = false;
            for(int j = i; !st[j]; j = a[j]){
                if(j == 0) flag = true;
                cnt++;
                st[j] = true;
                }
            if(!flag) ans += cnt + 1;
            else ans += cnt - 1;
            }
        }
    printf("%d\n", ans);
    return 0;
}