交换类题模板

交换次数 = 总个数 - 环的个数
环 = 由该数字指向应该在的位置所构成的环
例如3 5 1 2 4
3->1 5->4->2

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int  N =10010;
int b[N], st[N];
int n;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++) cin>>b[i];

    int cnt=0;

    for(int i=1; i<=n; i++)
        if(!st[i])
        {
            cnt++;
            for(int j=i ;!st[j]; j=b[j])
                st[j] = true;

        }
    printf("%d", n - cnt);

    return 0;
}