-并查集- [洛谷 P3420][POI2005]SKA-Piggy Banks

题目描述

Byteazar the Dragon拥有N个小猪存钱罐。每一个存钱罐能够用相应的钥匙打开或者被砸开。Byteazar已经将钥匙放入到一些存钱罐中。现在已知每个钥匙所在的存钱罐，Byteazar想要买一辆小汽车，而且需要打开所有的存钱罐。然而，他想要破坏尽量少的存钱罐，帮助Byteazar去决策最少要破坏多少存钱罐。

读入存钱罐的数量以及相应的钥匙的位置，求出能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量并将其输出。

输入格式

第一行：包括一个整数N（1<=N<=1000000)，这是Byteazar the Dragon拥有的存钱罐的数量。

存钱罐（包括它们对应的钥匙）从1到N编号。

接下来有N行：第i+1行包括一个整数x，表示第i个存钱罐对应的钥匙放置在了第x个存钱罐中。

输出格式

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

输入样例

4
2
1
2
4

输出样例

2

Solution

这道题可用并查集来做，把有对应钥匙的存钱罐和存这个钥匙的存钱罐合并到一个集合内，然后再求连通块的个数。

Code

#include<iostream>
#include<cstdio>
using namespace std;
int fa[1000003];
int find(int a){
    if(fa[a]==a) return a;
    else return fa[a]=find(fa[a]);
}
void un(int a,int b){
    a=find(a);
    b=find(b);
    fa[b]=a;
}
int main(){
    int n,a;
    cin>>n;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        un(i,a);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(fa[i]==i) ans++;
    }
    cout<<ans<<endl;
}