题目描述

算法1

(set) $O(n)$

思路：在一个环内的元素加入set，不在一个环的元素加入另一个set

C++ 代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
set<int> b[10010];
set<int> all;
int n;
int a[10010];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
    }
    int ind = 0;
    for (int i = 1; i <= n; i++) {
        if (all.find(a[i]) == all.end()) {  //没有遍历过这个点，直接加入一个新的set中
            ind++;
            int t_id = i;
            while (b[ind].find(a[t_id]) == b[ind].end()) {  //没有遍历过这个点，加入set，如果遍历过，则退出
                b[ind].insert(a[t_id]);
                all.insert(a[t_id]);
                t_id = a[t_id];
            }
        }
    }
    int sum = 0;
    for (int i = 1; i <= ind; i++) {
        int t = b[i].size();
        if (t >= 2) {  //若只有一个元素（不需要换），若大于等于2个，则换元素数目-1次
            sum += (t-1);
        }
    }
    cout << sum;
    return 0;
}