算法1

这题其实很巧，因为所有数最终都可以构成一个环，而最终的结果应该是每个数都单独成环，所以只要求出环的个数就是可以了，环的个数也是一个技巧，可以每次标记一下j,然后用b[j]上的是更新一下j,因为如果这个数字单独成环,j就等于b[j],否则就把b[j]上的数标记为环中的数

(图论) $O(n)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int b[N];
bool st[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;
        }
    cout << n - cnt << endl;
    return 0;
}