Bzoj1529/POI2005 ska Piggy banks

题目：ska Piggy banks

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1529

题目描述：Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.

分析：

　　（1）算法一：如果存钱罐i有存钱罐j的钥匙，就建一条（i->j）的有向边。然后就是缩点重构图后统计入度为0的连通块个数。最后就是华丽丽的Memory_Limit_Exceed了。

　　（2）算法二：如果存钱罐i的钥匙在存钱罐j里，就建一条（i->j）的有向边。然后就是缩点重构图后统计出度为0的连通块个数。由于所有点的出度均为1（即只有一条出边），可以用一个数组来保存每个点的出边，这样可以比建邻接表保存图节省空间。结果Accept。

　　（3）算法三：观察算法二建的图，分析该图的每一个子图，发现每一个子图有且只有一个环（圈），缩点后，这个环（圈）出度为0。问题转化为求一张图有几个连通块。考虑并查集。结果Accept。

代码：

这题IO量比较大，可以考虑读入优化，但我比较懒，不想写。

算法一：不想码。

算法二：

 1 #include <cstdio>
 2 #include <algorithm>
 3 int To[1000005];
 4 int TarjanTime,Dfn[1000005],Low[1000005],Stack[1000005];
 5 int Col[1000005],Out[1000005];
 6 void Tarjan(int v){
 7     Dfn[v]=Low[v]=++TarjanTime;
 8     Stack[++Stack[0]]=v;
 9     int u=To[v];
10     if(!Dfn[u]){
11         Tarjan(u);Low[v]=std::min(Low[v],Low[u]);
12     }else if(!Col[u])Low[v]=std::min(Low[v],Dfn[u]);
13     if(Dfn[v]==Low[v]){
14         ++Col[0];
15         for(;;){
16             u=Stack[Stack[0]--];
17             Col[u]=Col[0];
18             if(u==v)break;
19         }
20     }
21 }
22 int main(){
23     //freopen("in.txt","r",stdin);
24     //freopen("out.txt","w",stdout);
25     int n,ans;
26     scanf("%d",&n);
27     for(int i=1;i<=n;++i)scanf("%d",&To[i]);
28     for(int i=1;i<=n;++i)
29         if(!Dfn[i])Tarjan(i);
30     for(int i=1;i<=n;++i)
31         if(Col[i]!=Col[To[i]])
32             ++Out[Col[i]];
33     for(int i=1;i<=Col[0];++i)
34         if(!Out[i])++ans;
35     printf("%d",ans);
36     //fclose(stdin);fclose(stdout);
37     return 0;
38 }
39

算法三：

 1 #include <cstdio>
 2 int Set[1000005];
 3 int GetSet(int x){return Set[x]==x?x:Set[x]=GetSet(Set[x]);}
 4 int main(){
 5     //freopen("in.txt","r",stdin);
 6     //freopen("out.txt","w",stdout);
 7     int n,ans=0;
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;++i)Set[i]=i;
10     for(int i=1,to;i<=n;++i){
11         scanf("%d",&to);
12         Set[GetSet(i)]=GetSet(to);
13     }
14     for(int i=1;i<=n;++i)
15         ans+=(Set[i]==i);
16     printf("%d",ans);
17     //fclose(stdin);fclose(stdout);
18     return 0;
19 }