首页 > 代码库 > BZOJ 1529: [POI2005]ska Piggy banks [并查集]
BZOJ 1529: [POI2005]ska Piggy banks [并查集]
题意：
Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.
每个存钱罐只有一把钥匙...
和那道洛谷3月月赛R1T3长的一样的有向连通环套树...
任意连通分量环上一个点都可以到达全部点
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=1e6+5;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n, ans;int fa[N];int find(int x) {return x==fa[x] ? x : fa[x]=find(fa[x]);}int main() { freopen("in", "r", stdin); n=read(); for(int i=1; i<=n; i++) fa[i] = i; for(int i=1; i<=n; i++) fa[find(i)] = find(read()); for(int i=1; i<=n; i++) ans += fa[i]==i; printf("%d", ans);}
BZOJ 1529: [POI2005]ska Piggy banks [并查集]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。