题目

乐乐的 n 位朋友都拥有唯一的一个编号，编号分别为 1 至 n。某天按到达的时间顺序又给了一个顺序号，此时发现顺序号与多数的朋友编号不一致。乐乐想：如果俩俩交换顺序号，使得每位朋友的编号与顺序号相同，则最少需要交换几次？

输入：
包含二行：
第一行只有一个正整数：n，表示乐乐朋友的人数
第二行共有 n 个正整数，分别表示按顺序到达的朋友编号

输出：
只有一行且只有一个正整数：最少的交换次数

对于 30%的数据， 1 <= n <= 100
对于 80%的数据， 1 <= n <= 10 000
对于 100%的数据， 1 <= n <= 100 000

样例

样例输入

5  
4 2 1 5 3

样例输出

解析

画一个这样的图：把所有位置不正确的数字与它正确的位置连一个箭头。

比如说样例，他应该是：

我们可以利用离散数学图论中的入度和出度来理解这件事情：

一个数字如果在正确的位置上，那不可能有箭头指向这个位置，这个位置也不可能有箭头指向别的位置，我就是我，不一样的自我。也就是说入度和出度是0；
如果他不在自己的位置上，那它肯定指向某一个别的位置，并且另外一个位置上的数字肯定想回来，所以也有一个箭头指向这个位置，所以入度和出度都是1。

这样在全局上来看，肯定会导致我们可以连成一个或者若干个有向环，比如上图是样例连成的一个有向环。
这里需要说明的是，两个有向环之间必然是独立的，不可能有两个有向环有公共点。这是因为我们按照上面的逻辑分析入度出度，入度和出度都是1，哪儿来的公共点，要是公共了，入度和出度不就大于1了嘛。

不难想象，对于某一个有n个节点的有向环，还原成原本的样子需要移动的最小次数是n-1次。可以找规律验证（想想的话也不难想，因为1~n-2次移动只是帮助一个数字走到了他应该去的地方，但是第n-1次移动一下子帮助了俩数字）。

问题转换为，求所给区间有多少个有向环，以及每个有向环有多少个节点。每个有向环节点数减一再累加起来就是答案了。

有向环怎么找？可以遍历迭代。先从4看，4位置不对，看看4号位置是谁，是5，还是不对，看看5号位置，是3，还是不对，看看3号位置，是1，还是不对，看看1号位置，哦，又回到4了，那这就是个环。很明显，这个过程非常迭代，通过迭代一定能找到一个完整的有向环（~~就是我自己试了试好像挺容易写错的2333~~）。

代码

#include<iostream>

#define rep(a, b, c) for(int a=b;a<=c;i++)
#define max(a, b) a>b?a:b

using namespace std;

typedef long long ll;
const int N = 1008611;

int n, nums[N];
bool f[N];

int cnt(int index) {
    int pos = nums[index];
    f[index] = true;
    f[pos] = true;

    int t = 1;
    while (pos != index) {
        pos = nums[pos];
        f[pos] = true;
        t++;
    }
    return t;
}

ll ans = 0;

int main() {
    cin >> n;
    rep(i, 1, n) cin >> nums[i];

    rep(i, 1, n) {
        if (nums[i] != i && !f[i]) {
            int r = cnt(i) - 1;
            ans += max(0, r);
        }
    }

    cout << ans << endl;

    return 0;
}