分析

将一个乱序数组（1-n）恢复成递增序需要的最少交换次数

确定环的个数见注释

#include <iostream>
#include <cstring>
#include <algorithm>

#define ffor(i,s,e) for(int i=s;i<e;i++)
using namespace std;

const int N=1e5+5;
int a[N];
int nxt[N];
int flag[N];

int main(){
    int n;
    cin >> n;
    ffor(i,1,n+1){
        scanf("%d",&a[i]);
        nxt[a[i]]=i;
    }

    int cnt=0;//环的数量
    ffor(i,1,n+1){
        if(!flag[i]){//第一次出现
            cnt++;
            for(int p=a[i];!flag[p];p=nxt[p]){//标记该环内所有点
                flag[p]=1;
            }
        }
    }
    cout << n-cnt;
}