洛谷P3420 [POI2005]SKA-Piggy Banks 题解

题目链接：P3420 [POI2005]SKA-Piggy Banks

题意：

cxy 有 $n$ 个小猪存钱罐，每个存钱罐只能用钥匙打开或者砸开。cxy 已经把每个存钱罐的钥匙放到了某些存钱罐里。

cxy 现在想买一台汽车于是要把所有的钱都取出来。她想尽量少的打破存钱罐取出所有的钱，问最少要打破多少个存钱罐。

输入格式：

第一行包含一个正整数 $n (n\le10^6)$ ，表示存钱罐的总数。

接下来的 $n$ 行，每行一个整数，第 $i+1$ 行的整数代表第 $i$ 个存钱罐对应的钥匙放置的存钱罐编号。

输出格式：

输出一行一个整数，表示最少要打破多少个存钱罐。

我们可以把每个存钱罐 $u$ 向其钥匙所在的存钱罐 $v$ 建有向边。

不难发现这会形成一个基环内向树（森林），我们只要把环上的一个点敲掉就好了，可以用并查集维护。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6+15))

int n,f[N];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; for(int i=1; i<=n; i++) f[i] = i;
    for(int i=1,x; i<=n; i++) { cin >> x; f[find(i)] = find(x); }
    int res = 0; for(int i=1; i<=n; i++) res += (f[i]==i);
    cout << res << '\n';
    return 0;
}