BZOJ 1529: [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
Sample Output
2
In the foregoing example piggy banks 1 and 4 have to be smashed.
题解
看到Tarjan的标题我就点进去了、、然后MLE了、、、
这道题目使用并查集就好啦！
代码
|
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<cstdio> #include<bitset> using namespace std; const int Maxn=1000010; struct Edge{ int v,nxt; Edge(){} Edge(int a,int b){ v=a;nxt=b; } }; Edge e[Maxn]; int nume; int head[Maxn]; inline void addEdge(int u,int v){ e[++nume]=Edge(v,head[u]); head[u]=nume; } int low[Maxn],dfn[Maxn]; bitset<Maxn> vis,inque; int bel[Maxn]; int scc; int stack[Maxn]; int top; int ind; inline int remin(int a,int b){ if (a<b) return a; return b; } void tarjan(int x){ vis[x]=1; low[x]=dfn[x]=++ind; stack[++top]=x; inque[x]=1; for (int i=head[x];i;i=e[i].nxt){ int v=e[i].v; if (!vis[v]){ tarjan(v); low[x]=remin(low[x],low[v]); }else if (inque[v]){ low[x]=remin(low[x],dfn[v]); } } if (low[x]==dfn[x]){ scc++; int now=0; while(now!=x){ now=stack[top--]; bel[now]=scc; inque[now]=0; } } } int n; int inEdge[Maxn]; inline void rebuild(){ nume=0; for (int k=1;k<=n;k++){ for (int i=head[k];i;i=e[i].nxt){ int v=e[i].v; if (bel[v]!=bel[k])inEdge[bel[k]]++; } } } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ int x; scanf("%d",&x); addEdge(i,x); } for (int i=1;i<=n;i++) if (!vis[i]) tarjan(i); rebuild(); int Ans=0; for (int i=1;i<=scc;i++) if (!inEdge[i]) Ans++; printf("%d\n",Ans); return 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 |
#include<cstdio> using namespace std; const int Maxn=1000015; int father[Maxn]; inline void initFather(){ for (int i=1;i<Maxn;i++) father[i]=i; } int getFather(int x){ return father[x]=(father[x]==x?x:getFather(father[x])); } inline void mergeFather(int x,int y){ int fx=getFather(x),fy=getFather(y); if (fx==fy) return ; if (fx<fy) father[fx]=fy; else father[fy]=fx; } int n; int main(){ scanf("%d",&n); initFather(); for (int i=1;i<=n;i++){ int x; scanf("%d",&x); mergeFather(i,x); } int Ans=0; for (int i=1;i<=n;i++) if (father[i]==i) Ans++; printf("%d\n",Ans); return 0; } |
原文链接：BZOJ 1529: [POI2005]ska Piggy banks
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!