算法1

思路:情况一:交换同一个环内的点,则裂开成两个环
情况二:交换不成环中的两个点,则合并成一个环,最终答案是n-cnt

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=10010;


int n;//n个瓶子
int b[N];
bool st[N];//判重数组

int main(){
    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&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;
}