blablabla

样例

blablabla

算法1

查并集加环

所有摆放错位的数字最终可以形成多个环，设一个环内有x个数，则把环内数字恢复正确顺序需要x-1次排序，整个序列便是所有摆放错误的数字的个数减去环的个数。通过差并集找出所有环

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=10010;
int father[maxn];
int list[maxn];
bool st[maxn];
int findfather(int x){
    int a=x;
    while(father[x]!=x) x=father[x];
    int z=a;
    while(father[a]!=a){
        z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
int main(){
    int ans=0,fa=0;
    memset(st,false,sizeof(st));
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>list[i];
        father[i]=i;
    }
    for(int i=1;i<=n;i++){
        if(i!=list[i]) ans++;
        if(st[i]==true) continue;
        if(i!=list[i]){
            int temp=list[i];
            while(temp!=list[temp]&&st[temp]==false){
                father[temp]=findfather(i);
                st[temp]=true;
                temp=list[temp];
            }
        }
        st[i]=true;
    }
    for(int i=1;i<=n;i++){
        if(father[i]==i&&list[i]!=i) fa++;
    }
    printf("%d\n",ans-fa);
    return 0;
}