【bzoj1529】[POI2005]ska Piggy banks

2015.05.27 20:25 Wed | 22次阅读 | 旧日oi | 固定链接 | 源码

Description

Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.
N<=100000
题解
用并查集维护一下干掉一个瓶子最多能拿到多少东西,最后统计一下fa[i]=i的个数即可。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,x;
int fa[1000005];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        int p=find(i),q=find(x);
        if(p!=q) fa[q]=p;
    }
    int ans=0;
    for(int i=1;i<=n;i++) if(fa[i]==i) ans++;
    cout<<ans<<endl;
}```