「BZOJ1529」[POI2005] ska Piggy banks
Description
Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.
Input
第一行一个整数 N (1 <= N <= 1.000.000) – 表示存钱罐的总数. 接下来每行一个整数,第 i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.
Output
一个整数表示最少打破多少个存钱罐.
Sample Input
4
2
1
2
4
2
1
2
4
Sample Output
2
In the foregoing example piggy banks 1 and 4 have to be smashed.
题解
这题本来想练练tarjan的。。。
就是缩点重构图后统计入度为0的连通块个数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<iostream> #include<cstdio> #define N 1000005 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } int n,cnt,ind,ans,top; int head[N],h[N],r[N]; int scc,dfn[N],low[N],st[N],belong[N]; bool inst[N]; struct data{int to,next;}e[N],ed[N]; void insert(int u,int v) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;} void ins(int u,int v) {ed[++cnt].to=v;ed[cnt].next=h[u];h[u]=cnt;r[v]++;} void tarjan(int x) { int now=0; ind++;dfn[x]=low[x]=ind; st[++top]=x; inst[x]=1; for(int i=head[x];i;i=e[i].next) if(inst[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); else if(!dfn[e[i].to]) {tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);} if(dfn[x]==low[x]) { scc++; while(now!=x) { now=st[top--]; belong[now]=scc; inst[now]=0; } } } void rebuild() { cnt=0; for(int i=1;i<=n;i++) for(int j=head[i];j;j=e[j].next) if(belong[i]!=belong[e[j].to]) ins(belong[e[j].to],belong[i]); } int main() { n=read(); for(int i=1;i<=n;i++) insert(i,read()); for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); rebuild(); for(int i=1;i<=scc;i++) if(!r[i])ans++; printf("%d",ans); return 0; } |
但是此题会爆内存。。。
所以我们可以想到一种并查集的优越做法
合并完统计fa[i]=i的个数即可。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include<iostream> #include<cstdio> #define N 1000005 using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,ans; int fa[N]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} int main() { n=read(); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=n;i++) { int x=read(); int p=find(i),q=find(x); if(p!=q)fa[q]=i; } for(int i=1;i<=n;i++) if(fa[i]==i)ans++; printf("%d",ans); return 0; } |
Subscribe
计数器 9328223
OI 课件=>
OI 课件=>