本来以为是tarjan缩点……但是64MB的空间根本不足以存下原图和缩点后的新图。所以呢……并查集= =

  orz hzwer

MLE的tarjan:

 /**************************************************************
Problem: 1529
User: Tunix
Language: C++
Result: Memory_Limit_Exceed
****************************************************************/ //BZOJ 1529
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=; void read(int &v){
v=;int sign=; char ch=getchar();
while(ch<'' || ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){v=v*+ch-''; ch=getchar();}
v*=sign;
}
/********************tamplate*******************/
int dfn[N],low[N],dfs_clock,SCC=,belong[N],n;
int head[N],to[N],next[N],cnt;
void ins(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;
}
int t[N],ne[N],h[N];
void add(int x,int y){
t[++cnt]=y; ne[cnt]=h[x]; h[x]=cnt;
}
bool inst[N];
int st[N],top=;
void tarjan(int x){
int y;
dfn[x]=low[x]=++dfs_clock;
st[top++]=x;
inst[x]=;
for(int i=head[x];i;i=next[i]){
y=to[i];
if (!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if (inst[y]) low[x]=min(low[x],dfn[y]);
}
if (dfn[x]==low[x]){
++SCC;
for(y=;y!=x;){
y=st[--top];
inst[y]=;
belong[y]=SCC;
}
}
}
int in[N];
void rebuild(){
F(x,,n)
for(int i=head[x];i;i=next[i])
if (belong[x]!=belong[to[i]]){
add(belong[x],belong[to[i]]);
in[belong[to[i]]]++;
}
}
/***********************************************/ int main(){
#ifndef ONLINE_JUDGE
freopen("1529.in","r",stdin);
#endif
read(n);
int x;
F(i,,n){
read(x);
ins(x,i);
}
F(i,,n) if (!dfn[i]) tarjan(i);
rebuild();
int ans=;
F(i,,SCC) if(in[i]==) ans++;
printf("%d\n",ans);
return ;
}

并查集:

 /**************************************************************
Problem: 1529
User: Tunix
Language: C++
Result: Accepted
Time:908 ms
Memory:4712 kb
****************************************************************/ //BZOJ 1529
#include<cstdio>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=; void read(int &v){
v=;int sign=; char ch=getchar();
while(ch<'' || ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){v=v*+ch-''; ch=getchar();}
v*=sign;
}
int fa[N],n;
int getfather(int x){
if (fa[x]!=x) fa[x]=getfather(fa[x]);
return fa[x];
}
int main(){
read(n);
int x;
F(i,,n) fa[i]=i;
F(i,,n){
read(x);
int f1=getfather(i),f2=getfather(x);
if (f1!=f2) fa[f1]=f2;
}
int ans=;
F(i,,n) if (fa[i]==i) ans++;
printf("%d\n",ans);
return ;
}

最新文章

  1. Git学习笔记与IntelliJ IDEA整合
  2. MySQL 5.7 Replication 相关新功能说明
  3. 【JSOI2007】【Bzoj1029】建筑抢修
  4. iOS滤镜实现之LOMO(美图秀秀经典LOMO)
  5. 1125mysqbinlog日志
  6. JAVA设计模式--工厂方法模式
  7. Bootstrap+angularjs+MVC3+分页技术+角色权限验证系统
  8. 【题解】【排列组合】【回溯】【Leetcode】Generate Parentheses
  9. twitter bootstrap 2.x 3.x区别
  10. 【转】ASP.NET MVC 入门教程列表
  11. RocksDB上锁机制
  12. 基于 EntityFramework、Autofac 的 UnitOfWork 框架(一)
  13. [九省联考2018]IIIDX
  14. windows 环境下mysql 重置密码解决方案
  15. Flip String to Monotone Increasing LT926
  16. 音乐app各部分笔记(二)
  17. MATLAB 图形着色
  18. Windows安装nginx服务
  19. Android高级控件(上)
  20. 学习node.js的C++扩展

热门文章

  1. log4net自定义字段写入SqlServer数据库 ASP.net
  2. 安装MySQL软件
  3. 【风马一族_Android】造作app的效果图
  4. 弹性布局-flex
  5. 理解 pkg-config 工具
  6. Fedora 20 创建桌面快捷方式
  7. jQuery的toggle()的自动触发真烦人
  8. WIN10主动推升级,有点意思
  9. fastclick插件 导致 input[type=&quot;date&quot;] 无法触发问题解决方案
  10. Unity3d 动态批处理的问题