自动搬运

查看原文

来自洛谷，原作者为

	李尧 **

搬运于2025-08-24 21:48:50，当前版本为作者最后更新于2018-09-15 22:40:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实这题很简单的

所以你第一次为什么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; 
}