题解 P3420 【[POI2005]SKA-Piggy Banks】

· · 题解

其实这题很简单的

所以你第一次为什么TLE90分

在此忠告大家，一定要在过程中更新fa[x]的值（我相信你们写的都是并查集）

现在288ms，感觉自己棒棒哒~

这个题目主要的难点在于如何判定破哪个罐子。其实不难想，如果出现环形，那么一定要破掉一个罐子。

那么，什么时候会出现环形呢？

想一下，如果一个罐子i的钥匙为j，而我们已知只要打开i就能打开j（即find（j）==i），那么我们必须破开i，或者破开j，暂时我选择破开i。

放代码喽，不要直接复制哦~

#include <bits/stdc++.h>
using namespace std;
int n,a[1000007],ans;
int fa[1000007];
int find(int x){
    if(fa[x]==x) return x;
    int a=find(fa[x]);
    return fa[x]=a;
}//在寻找fa[x]的过程中更新fa[x]的值，减短下一次寻找的线路，防止TLE
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) fa[i]=i;//初始化
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);  
        if(find(a[i])==i){//判定是否构环
            fa[i]=i;ans++;//如果构环，则破掉i号存钱罐
        }
        else fa[i]=a[i];//反之，把i的“父亲”赋为a[i]
    }
    printf("%d",ans);//输出破掉的次数
    return 0; 
}