题目描述

小怡拥有N个小猪存钱罐。每一个存钱罐能够用相应的钥匙打开或者被砸开。小怡已经将钥匙放入到一些存钱罐中。现在已知每个钥匙所在的存钱罐，小怡想要买一辆小汽车，而且需要打开所有的存钱罐。然而，他想要破坏尽量少的存钱罐，帮助小怡去决策最少要破坏多少存钱罐。
写一段程序包括：
读入存钱罐的数量以及相应的钥匙的位置，求出能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量并将其输出。

输入
第一行：包括一个整数N（1<=N<=1000000)，这是小怡拥有的存钱罐的数量。
存钱罐（包括它们对应的钥匙）从1到N编号。
接下来有N行：第i+1行包括一个整数x，表示第i个存钱罐对应的钥匙放置在了第x个存钱罐中。

输出
仅一行：包括一个整数，表示能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量。

样例

输入

4
2
1
2
4

输出

2

每个数入度必为1

拓展：置换群法，每个数入度必为一找环 https://www.acwing.com/blog/content/19790/

并查集找环

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;
int p[N];
int n;

int find(int x)
{
    if (x != p[x]){p[x] = find(p[x]);}
    return p[x];
}

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

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        int pi = find(i), px = find(x);
        p[px] = pi;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (p[i] == i) cnt ++;
    printf("%d\n", cnt);
    return 0;
}