首页 > 代码库 > 【BZOJ】1529 [POI2005]ska Piggy banks
【BZOJ】1529 [POI2005]ska Piggy banks
【算法】（强连通分量）并查集
【题解】
1.用tarjan计算强连通分量并缩点，在新图中找入度为0的点的个数就是答案。
但是，会爆内存（题目内存限制64MB）。
2.用并查集，最后从1到n统计fa[i]==i的数量即是答案。
（tarjan）
#include<cstdio>#include<algorithm>using namespace std;const int maxn=1000010;struct edge{int u,v,from;}e[maxn];int n,tot,top,mark,color,col[maxn],dfn[maxn],low[maxn],s[maxn],lack[maxn],in[maxn],first[maxn];void insert(int u,int v){tot++;e[tot].u=u;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void tarjan(int x){ dfn[x]=low[x]=++mark; s[++top]=x;lack[x]=top; for(int i=first[x];i;i=e[i].from) { int y=e[i].v; if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if(!col[y])low[x]=min(low[x],dfn[y]); } if(dfn[x]==low[x]) { color++; for(int i=lack[x];i<=top;i++)col[s[i]]=color; top=lack[x]-1; }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { int u; scanf("%d",&u); insert(u,i); } for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); for(int i=1;i<=tot;i++) if(col[e[i].u]!=col[e[i].v])in[col[e[i].v]]++; int ans=0; for(int i=1;i<=color;i++)if(in[i]==0)ans++; printf("%d",ans); return 0;}
（并查集）
#include<cstdio>#include<algorithm>using namespace std;const int maxn=1000010;int f[maxn],n;int getfa(int x){return f[x]==x?x:f[x]=getfa(f[x]);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=n;i++) { int u; scanf("%d",&u); if(getfa(i)!=getfa(u))f[f[i]]=f[u]; } int ans=0; for(int i=1;i<=n;i++)if(f[i]==i)ans++; printf("%d",ans); return 0;}
并查集记得初始化fa[i]=i。
【BZOJ】1529 [POI2005]ska Piggy banks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。